Enumeration and generation with a string automata representation

DOI10.1016/j.tcs.2007.07.029zbMath1143.68031OpenAlexW2090028629MaRDI QIDQ2465040

Rogério Reis, Nelma Moreira, Marco Almeida

Publication date: 19 December 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.029

zbMATH Keywords

finite automatarandom generationexact enumerationminimal automatainitially-connected deterministic finite automata

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Formal languages and automata (68Q45)

Related Items

Random Deterministic Automata ⋮ Generating, sampling and counting subclasses of regular tree languages ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Empirical studies in the size of diagnosers and verifiers for diagnosability analysis ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA ⋮ Succinct representations for (non)deterministic finite automata ⋮ Incomplete operational transition complexity of regular languages ⋮ STATE COMPLEXITY AND APPROXIMATION ⋮ Incremental DFA Minimisation ⋮ COMPAS - A Computing Package for Synchronization ⋮ A Challenging Family of Automata for Classical Minimization Algorithms ⋮ Short Regular Expressions from Finite Automata: Empirical Results ⋮ Semicomputable points in Euclidean spaces ⋮ ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED ⋮ Enumerating regular expressions and their languages ⋮ Succinct representation for (non)deterministic finite automata

Uses Software

• OEIS

Cites Work

• Enumeration and random generation of accessible automata
• Random generation of DFAs
• Exact enumeration of acyclic deterministic automata
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• A Census of Finite Automata
• Enumeration of finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item