| Resumo: |
Os autómatos e as linguagens formais são omnipresentes na Ciência de Computadores. Apesar do seu poder expressivo relativamente limitado, as linguagens regulares são importantes em muitas áreas. Com um número crescente de aplicações a complexidade descritiva das linguagens formais tornou-se uma importante área de investigação nos últimos 25 anos. Dada uma medida, a complexidade descritiva de uma linguagem é o tamanho da sua menor representação. É importante saber como esse tamanho varia quando várias dessas representações são combinadas ou transformadas, uma vez que isso influência o desempenho e a quantidade de recursos exigidos pelas aplicações. Em geral, ter objetos mais pequenos melhora o nosso controle sobre o software, tornando-o mais simples, mais eficiente e fiável.
Os modelos computacionais ou são determinísticos ou não. Mesmo para autómatos finitos, onde autómatos determinísticos (DFAs) e não determinísticos (NFAs) têm o mesmo poder expressivo, há um "trade-off" entre a complexidade descritiva e computacional. Os NFAs podem fornecer uma descrição exponencialmente mais sucinta que os DFAs. Por outro lado, muitos problemas de decisão que são solucionáveis em tempo polinomial para os DFAs, como a equivalência, inclusão e universalidade, são computacionalmente difíceis para os NFAs [JR93].
A maioria dos estudos nesta área consideram a complexidade no pior caso. No entanto, para aplicações práticas a análise no caso médio fornece informações mais precisas sobre os recursos necessários. Infelizmente, até ao momento, não houve muito progresso nesta direção.
Tentando colmatar essa falha e aproveitando os conhecimentos e experiência da equipa nesta área, o tópico central desta proposta é a complexidade descritiva de linguagens e operações regulares, no caso médio. Recentemente estudamos o tamanho médio de NFAs que resultam de diferentes construções a partir de uma expressão regular (RE), usando como ferramenta de estudo a análise combinatória  |
Resumo
Os autómatos e as linguagens formais são omnipresentes na Ciência de Computadores. Apesar do seu poder expressivo relativamente limitado, as linguagens regulares são importantes em muitas áreas. Com um número crescente de aplicações a complexidade descritiva das linguagens formais tornou-se uma importante área de investigação nos últimos 25 anos. Dada uma medida, a complexidade descritiva de uma linguagem é o tamanho da sua menor representação. É importante saber como esse tamanho varia quando várias dessas representações são combinadas ou transformadas, uma vez que isso influência o desempenho e a quantidade de recursos exigidos pelas aplicações. Em geral, ter objetos mais pequenos melhora o nosso controle sobre o software, tornando-o mais simples, mais eficiente e fiável.
Os modelos computacionais ou são determinísticos ou não. Mesmo para autómatos finitos, onde autómatos determinísticos (DFAs) e não determinísticos (NFAs) têm o mesmo poder expressivo, há um "trade-off" entre a complexidade descritiva e computacional. Os NFAs podem fornecer uma descrição exponencialmente mais sucinta que os DFAs. Por outro lado, muitos problemas de decisão que são solucionáveis em tempo polinomial para os DFAs, como a equivalência, inclusão e universalidade, são computacionalmente difíceis para os NFAs [JR93].
A maioria dos estudos nesta área consideram a complexidade no pior caso. No entanto, para aplicações práticas a análise no caso médio fornece informações mais precisas sobre os recursos necessários. Infelizmente, até ao momento, não houve muito progresso nesta direção.
Tentando colmatar essa falha e aproveitando os conhecimentos e experiência da equipa nesta área, o tópico central desta proposta é a complexidade descritiva de linguagens e operações regulares, no caso médio. Recentemente estudamos o tamanho médio de NFAs que resultam de diferentes construções a partir de uma expressão regular (RE), usando como ferramenta de estudo a análise combinatória [BMMR12, BBMMR17, BMMR18]. Nalguns casos, é necessário usar funções geradoras implicitamente definidas por curvas algébricas e desenvolvemos novos métodos para extrair a informação necessária para as estimativas assimptóticas [BMMR19, KMMR20, BMMR20]. As novas técnicas serão cruciais para abordar o problema da complexidade no caso médio da determinização de NFAs, da qual a complexidade operacional depende fortemente.
A complexidade de estados de uma linguagem regular é dada pelo número de estados do seu DFA mínimo. A complexidade de estados de uma operação sobre linguagens regulares é a complexidade de estados da linguagem que resulta da operação, considerada como função das complexidades de estados dos seus operandos. Por exemplo, dados dois DFAs com complexidades de estados n e m, para obter um DFA para a linguagem da concatenação, determina-se primeiro um NFA para a concatenação, de seguida é determinizado e depois minimizado. O número de estados f(n,m) do autómato final é então a complexidade de estados da operação de concatenação. O passo de maior complexidade é o processo de determinização. Outro problema que gostaríamos de abordar é o estudo da complexidade descritiva de diferentes operações para modelos cujo grau de não- determinismo é limitado.
Neste contexto a noção de não-ambiguidade também desempenha um papel importante [HSS17]. Ambiguidade é um conceito fundamental em análise sintática, encaixe de padrões, XML e segurança [WBMW16,GM17]. Muitas aplicações utilizam REs como representação para linguagens regulares. A construção de NFAs a partir de REs é quadrática. Várias classes de REs não ambíguas (determinísticas (DREs)) foram estudadas [GM17]. Usando conversões baseadas em derivadas, estendemos algumas dessas classes, mas aqui o objetivo é o desenvolvimento de algoritmos de decisão fiáveis para classes restritas d REs.
Um desafio das aplicações atuais é a grande dimensão (e diversidade) dos alfabetos utilizados. Isso torna-se particularmente crítico em algoritmos de aprendizagem máquina, que utilizam expressões regulares como descrição da linguagem natural [PKCH19, MLV21]. Para obter representações sucintas quando os alfabetos são grandes, introduzimos autómatos e expressões com etiquetas invariantes [KMRY20]. Neste projeto, estudaremos a complexidade descritiva dos modelos resultantes, ou seja, quando operados.
Resumindo, neste projeto pretendemos avançar no conhecimento da complexidade no estado médio para problemas fundamentais de diversos algoritmos baseados em autómatos com aplicações extensas. Com base nos conhecimentos e competências da equipa na área, esperamos contribuir também para o desenvolvimento de métodos mais eficientes, baseados em autómatos, através de uma análise detalhada de várias subclasses. A inovação principal é pela primeira vez tentar obter resultados no caso médio sobre a determinação de autómatos. |