Enumeration and generation with a string automata representation

DOI10.1016/J.TCS.2007.07.029MaRDI QIDQ2465040zbMATH OpenOpenAlexFDO

Authors Marco Almeida, Nelma Moreira, Rogério Reis

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

exact enumerationfinite automatainitially-connected deterministic finite automataminimal automatarandom generation

Mathematics Subject Classification ID

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

Recommendations

• EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
• Enumeration and random generation of possibly incomplete deterministic automata
• Enumeration and random generation of accessible automata
• Random generation of DFAs
• Accessible and deterministic automata: enumeration and Boltzmann samplers

Cites work

• A Census of Finite Automata
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Enumeration and random generation of accessible automata
• Enumeration of finite automata
• Exact enumeration of acyclic deterministic automata
• scientific article; zbMATH DE number 2186886 (Why is no real title available?)
• scientific article; zbMATH DE number 2186907 (Why is no real title available?)
• scientific article; zbMATH DE number 3645067 (Why is no real title available?)
• scientific article; zbMATH DE number 5605090 (Why is no real title available?)
• scientific article; zbMATH DE number 3913686 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2068873 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• Random generation of DFAs

Cited in

(29)

• Empirical studies in the size of diagnosers and verifiers for diagnosability analysis
• Enumerating regular expressions and their languages
• Succinct representation for (non)deterministic finite automata
• Succinct representations for (non)deterministic finite automata
• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• Random deterministic automata
• On the uniform random generation of non deterministic automata up to isomorphism
• Incremental DFA minimisation
• COMPAS -- a computing package for synchronization
• A challenging family of automata for classical minimization algorithms
• ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED
• EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
• Generating, sampling and counting subclasses of regular tree languages
• Short Regular Expressions from Finite Automata: Empirical Results
• scientific article; zbMATH DE number 3974323 (Why is no real title available?)
• Primitive digraphs with large exponents and slowly synchronizing automata
• Edmonds-Karp
• Flow Networks
• Gabow SCC
• Generation of Well-Formed Parenthesis Strings in Constant Worst-Case Time
• String Analysis via Automata Manipulation with Logic Circuit Representation
• State complexity and approximation
• On String Languages Generated by Sequential Numerical P Systems
• Incomplete operational transition complexity of regular languages
• Semicomputable points in Euclidean spaces
• Prpu_Maxflow
• Small balanced vertex separators in NFA to regular expression conversion
• Forward injective finite automata: exact and random generation of nonisomorphic NFAs
• Enumeration and random generation of accessible automata

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Enumeration and generation with a string automata representation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465040)