Exact generation of acyclic deterministic finite automata

2009/08/23 by Marco Almeida, Almeida, Marco, Nelma Moreira +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0908.3315

openalex publication_date 2009/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a canonical representation for trim acyclic deterministic finite automata (Adfa) with n states over an alphabet of k symbols. Using this normal form, we present a backtracking algorithm for the exact generation of Adfas. This algorithm is a non trivial adaptation of the algorithm for the exact generation of minimal acyclic deterministic finite automata, presented by Almeida et al.

Related

• Incremental Construction of Compact Acyclic NFAs
• Incremental construction of minimal acyclic finite-state automata
• On the Representation of Finite Automata
• Aspects of enumeration and generation with a string automata representation
• From regular expressions to deterministic finite automata: 2^(n)/(2)+√(n)(log n)^Θ(1) states are necessary and sufficient