2024/02/01 by Roberto Gorrieri, Gorrieri, Roberto
Computer Science · #Natural Language Processing Techniques #Multi-Agent Systems and Negotiation
paper · pdf · doi:10.48550/arxiv.2402.00502
A subclass of nondeterministic Finite Automata generated by means of regular Grammars (GFAs, for short) is introduced. A process algebra is proposed, whose semantics maps a term to a GFA. We prove a representability theorem: for each GFA N, there exists a process algebraic term p such that its semantics is a GFA isomorphic to N. Moreover, we provide a concise axiomatization of language equivalence: two GFAs N1 and N2 recognize the same regular 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 2 conditional axioms, only.