Exact enumeration of acyclic deterministic automata

DOI10.1016/J.DAM.2005.06.009MaRDI QIDQ2489949zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Valery A. Liskovets

Publication date 28 April 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.06.009

zbMATH Keywords

Dead stateEnumerative injection methodInitially connected automatonMinimal automaton recognizing a finite languageQuasi-acyclic automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Enumeration of minimal acyclic automata via generalized parking functions
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES
• Minimisation of acyclic deterministic automata in linear time
• scientific article; zbMATH DE number 3913686
• scientific article; zbMATH DE number 1948499

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2068873 (Why is no real title available?)
• scientific article; zbMATH DE number 3294293 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Direct construction of minimal acyclic finite states automata
• Enumeration of Linear Graphs for Mappings of Finite Sets
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Minimisation of acyclic deterministic automata in linear time
• On the Number of Maximal Vertices of a Random Acyclic Digraph
• On the shape of a random acyclic digraph
• Pseudo-minimal transducer
• The asymptotic number of acyclic digraphs. II

Cited in

(21)

• An algorithm for enumerating all infinite repetitions in a D0L-system
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES
• Compacted binary trees admit a stretched exponential
• Succinct representations for (non)deterministic finite automata
• Succinct representation for (non)deterministic finite automata
• Random generation of deterministic acyclic automata using Markov chains
• Enumeration of minimal acyclic automata via generalized parking functions
• The method of forced enumeration for nondeterministic automata
• Sampling different kinds of acyclic automata using Markov chains
• Enumeration and generation with a string automata representation
• A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata
• Random generation and enumeration of accessible deterministic real-time pushdown automata
• Minimisation of acyclic deterministic automata in linear time
• Enumerated BSP Automata
• scientific article; zbMATH DE number 3913686 (Why is no real title available?)
• Enumerating regular expressions and their languages
• Asymptotic enumeration of minimal automata
• Counting extensional acyclic digraphs
• scientific article; zbMATH DE number 3934415 (Why is no real title available?)
• EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
• Asymptotic enumeration of compacted binary trees of bounded right height

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Exact enumeration of acyclic deterministic automata

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