Linguagens regulares do ponto de vista teórico da categoria

21

Percebi que as línguas regulares sobre o alfabeto podem ser pensadas naturalmente como um poset e, de fato, uma treliça. Além disso, a concatenação junto com o idioma vazio ϵ define uma estrutura monoidal estrita nessa categoria que é distributiva sobre junções (não tenho certeza sobre os encontros). Essa é uma construção útil na teoria ou prática de linguagens regulares? Existem algumas boas sugestões a serem encontradas, por exemplo, podemos definir a estrela Kleene como uma?Σϵ

Esta é uma cópia de uma pergunta feita no curso de Compiladores do Coursera: https://class.coursera.org/compilers/forum/thread?thread_id=311

Alexei Averchenko
fonte
4
Apenas salientando que o link exige que alguém possa fazer login no site do Coursea.
Dave Clarke
11
Qual é a ordem parcial que transforma idiomas regulares em posets? é apenas a propriedade do subconjunto?
Suresh Venkat
@ Suresh Sim, estou faltando alguma coisa?
Alexei Averchenko
11
Não, eu só queria entender se havia algo mais específico para a estrutura da linguagem
Suresh Venkat
@Suresh Eu certamente não sou tão esperto ou educado como referências as pessoas Dave Clarke, então eu só vi a coisa óbvia mais :)
Alexei Averchenko

Respostas:

18

Muito foi feito aplicando a teoria das categorias a linguagens e autômatos regulares. Um ponto de partida são os trabalhos recentes:

No primeiro desses artigos, a estrutura das expressões regulares é tratada algebricamente e as linguagens geradas são tratadas coalgebraicamente. Essas duas visualizações são integradas em um cenário bialgebraico. Uma bialgebra é um par álgebra-coalgebra com uma lei distributiva adequada que captura a interação entre os termos sintáticos (expressões regulares) e o comportamento computacional (linguagens geradas). A base deste artigo é álgebra e coalgebra, como tratado em ciência da computação sob os guarda-chuvas da álgebra universal e da coalgebra, em vez do que se vê em matemática (grupos etc.).

O segundo artigo utiliza técnicas que vêm do tratamento matemático mais tradicional da álgebra (módulos etc.) e da coalgebra, mas receio não conhecer os detalhes.

Nem trata a estrela Kleene como um complemento, até onde eu sei.

De maneira mais geral, há muito trabalho aplicando a teoria de categorias para automatizar, em vez de expressões regulares. Uma amostra deste trabalho inclui:

Finalmente, há o trabalho sobre teorias da iteração, teorias da iteração: a lógica equacional dos processos iterativos de Stephen L. Bloom e Zoltán Ésik, que se concentra na iteração (por exemplo, estrela Kleene), mas de uma perspectiva mais geral, onde as linguagens regulares são apenas uma coisa que se enquadra na teoria.

Dave Clarke
fonte
2
Para autômatos, também há books.google.co.uk/…
Radu GRIGore
11
Infelizmente, o termo "álgebra" é usado em excesso. Existe o significado de "álgebra" como uma estrutura algébrica genérica, usada em álgebra universal, álgebras de functor e álgebras de mônada. O jornal de Bart Jacobs está falando sobre isso. Existe uma estrutura mais específica chamada " álgebra " definida na teoria dos anéis / módulos. O artigo de James Worthington está lidando com isso. Na minha opinião, o trabalho de Worthington é muito mais interessante, mas acho que apenas começamos a arranhar a superfície aqui.
Uday Reddy
Link não paywall para o artigo de Bart: repository.ubn.ru.nl/handle/2066/36207
Turion
12

Na verdade, acho que o que você está procurando é a álgebra de Kleene. Veja o artigo clássico de Dexter Kozen. Ele dá uma axiomatização da estrela Kleene. Presumo que este seja o primeiro passo no qual você está interessado.

Um teorema da completude para álgebras de Kleene e a álgebra de eventos regulares. Information and Computation, 110 (2): 366-390, maio de 1994.

Esse artigo não utiliza a teoria das categorias, mas fornece uma axiomatização equacional das álgebras de Kleene, cuja estrutura inclui a das linguagens regulares. As álgebras Kleene com testes podem ser vistas como a extensão de expressões regulares para modelar programas simples com loops e condicionais (mas sem atribuições). Essa extensão é útil para raciocinar sobre esses programas simples de maneira puramente algébrica.

Na teoria coalgebraica da álgebra de Kleene com testes. Relatório técnico. Universidade de Cornell, março de 2008.

Linguagens regulares formam uma álgebra booleana com estrutura adicional, como você observa. Essa estrutura foi estudada do ponto de vista da dualidade de Stone por Nick Pippenger.

Línguas regulares e dualidade de pedra . Nicholas Pippenger. Teoria Computing Systems, 1997: 121-134.

A abordagem de dualidade do reconhecimento de idiomas tem sido destaque recentemente e foi aplicada para obter novos resultados sobre o reconhecimento de idiomas.

Dualidade e teoria equacional das linguagens regulares. M. Gehrke, S. Grigorieff, J.-E. PIN.

Vijay D
fonte
11
E especificamente sobre alguns adjunções clássicos de álgebras de Kleene na teoria da máquina: cs.cornell.edu/Courses/cs786/2004sp/Lectures/l06-adj.pdf
ex0du5
4

Olhar para o mundo usando óculos de teoria da categoria é chamado de categorização . Às vezes, produz resultados realmente agradáveis ​​e surpreendentes. Os físicos começaram a dizer que pensar em um grupo como um gropóide de um elemento faz uma diferença muito grande . Estou começando a perceber que pensar em um monóide como uma categoria de um elemento também simplifica muitas coisas. (Por exemplo, uma ação monóide é, então, um functor em Set . Essas coisas formam categorias e toposes fechadas por cartesianos. Portanto, elas têm um cálculo lambda e uma lógica intuicionista também!)

Você deseja categorizar idiomas regulares. Não sei se isso foi feito ou se foi considerado desinteressante. Eu não vi nada escrito sobre isso. No entanto, a estrutura algébrica de linguagens regulares, álgebras Kleene, é suficientemente interessante. Há uma vasta quantidade de literatura sobre eles. Mas, na minha opinião, a teoria das linguagens regulares e dos autômatos finitos sofre de um compromisso prematuro com a finitude. (Grupos finitos são interessantes e importantes, mas você não deseja que a definição de "grupo" se comprometa com a finitude desde o início.) Portanto, seria útil descartar a finitude e estudar as estruturas de maneira mais geral.

O trabalho mais interessante em andamento no momento está relacionado a estruturas denominadas bimonoides de localidade definidas por Hoare. Verificou-se que álgebras de Kleene concorrentes são um exemplo delas . Bimonoides e simultaneidade de localidade são uma direção de pesquisa ativa.

Uday Reddy
fonte