Linguagens regulares do ponto de vista teórico da categoria

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?$\Sigma$$\epsilon$

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

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

• Revisão Bialgebraica de Autômatos Determinísticos, Expressões Regulares e Idiomas por Bart Jacobs
• Uma abordagem bialgebraica dos autômatos e da teoria formal da linguagem de James Worthington.

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:

• Bloom SL; Sabadini N .; Matrizes, máquinas e comportamentos RFC de Walters . Estruturas categóricas aplicadas, volume 4, número 4, dezembro de 1996, pp. 343-360 (18)

• Michael A. Arbib, Ernest G. Manes: A visão de um categorista de autômatos e sistemas. Teoria da categoria aplicada à computação e controle 1974: 51-64

• MA Arbib e EG Manes. Máquinas adjuntas, máquinas de comportamento estatal e dualidade . Jornal de Álgebra Pura e Aplicada, 6: 313-344, 1975.

• MA Arbib e EG Manes. Máquinas em uma categoria . Jornal de Álgebra Pura e Aplicada, 19: 9-20, 1980.
• O livro de Jirí Adámek e Vera Trnková, Automata and Algebras in Categories , como apontado em um comentário .

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.

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.

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.