We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
Piedeleu R., Zanasi F. (2023). A FINITE AXIOMATISATION OF FINITE-STATE AUTOMATA USING STRING DIAGRAMS. LOGICAL METHODS IN COMPUTER SCIENCE, 19(1), 1-40 [10.46298/lmcs-19(1:13)2023].
A FINITE AXIOMATISATION OF FINITE-STATE AUTOMATA USING STRING DIAGRAMS
Zanasi F.
2023
Abstract
We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.| File | Dimensione | Formato | |
|---|---|---|---|
|
2211.16484.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
792.51 kB
Formato
Adobe PDF
|
792.51 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
