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— a result which is provably impossible for the one-dimensional syntax of regular expressions. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.

Piedeleu R., Zanasi F. (2021). A string diagrammatic axiomatisation of finite-state automata. GEWERBESTRASSE 11, CHAM : Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-71995-1_24].

A string diagrammatic axiomatisation of finite-state automata

Zanasi F.
2021

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— a result which is provably impossible for the one-dimensional syntax of regular expressions. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
2021
Foundations of Software Science and Computation Structures. FOSSACS 2021
469
489
Piedeleu R., Zanasi F. (2021). A string diagrammatic axiomatisation of finite-state automata. GEWERBESTRASSE 11, CHAM : Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-71995-1_24].
Piedeleu R.; Zanasi F.
File in questo prodotto:
File Dimensione Formato  
978-3-030-71995-1_24.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 420.96 kB
Formato Adobe PDF
420.96 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/904860
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact