A process algebra is proposed, whose semantics maps a term to a nondeterministic finite automaton (NFA, for short). We prove a representability theorem: for each NFA N, there exists a process algebraic term p such that its semantics is an NFA isomorphic to N. Moreover, we provide a concise axiomatization of language equivalence: two NFAs N1 and N2 recognize the same language if and only if the associated terms p1 and p2, respectively, can be equated by means of a set of axioms, comprising 7 axioms plus 3 conditional axioms, only.
Gorrieri, R. (2025). An algebraic theory of nondeterministic finite automata. THE JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING, 145, 1-23 [10.1016/j.jlamp.2025.101055].
An algebraic theory of nondeterministic finite automata
Gorrieri R.
Primo
Formal Analysis
2025
Abstract
A process algebra is proposed, whose semantics maps a term to a nondeterministic finite automaton (NFA, for short). We prove a representability theorem: for each NFA N, there exists a process algebraic term p such that its semantics is an NFA isomorphic to N. Moreover, we provide a concise axiomatization of language equivalence: two NFAs N1 and N2 recognize the same language if and only if the associated terms p1 and p2, respectively, can be equated by means of a set of axioms, comprising 7 axioms plus 3 conditional axioms, only.| File | Dimensione | Formato | |
|---|---|---|---|
|
nfa-jlamp.pdf
embargo fino al 23/02/2026
Tipo:
Postprint / Author's Accepted Manuscript (AAM) - versione accettata per la pubblicazione dopo la peer-review
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione
292.15 kB
Formato
Adobe PDF
|
292.15 kB | Adobe PDF | Visualizza/Apri Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
