2023/01/09 by Gorrieri, Roberto
#68Q45 #68Q85 #F.1.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2301.03435
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.