Exact enumeration of acyclic deterministic automata

DOI10.1016/j.dam.2005.06.009zbMath1090.68060OpenAlexW2056679539WikidataQ60692131 ScholiaQ60692131MaRDI QIDQ2489949

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)

Related Items (11)

Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata ⋮ Counting extensional acyclic digraphs ⋮ Sampling different kinds of acyclic automata using Markov chains ⋮ EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA ⋮ Succinct representations for (non)deterministic finite automata ⋮ Enumeration and generation with a string automata representation ⋮ Compacted binary trees admit a stretched exponential ⋮ Random Generation of Deterministic Acyclic Automata Using Markov Chains ⋮ Asymptotic enumeration of compacted binary trees of bounded right height ⋮ Enumerating regular expressions and their languages ⋮ Succinct representation for (non)deterministic finite automata

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The asymptotic number of acyclic digraphs. II
• Minimisation of acyclic deterministic automata in linear time
• Pseudo-minimal transducer
• On the shape of a random acyclic digraph
• On the Number of Maximal Vertices of a Random Acyclic Digraph
• Incremental Construction of Minimal Acyclic Finite-State Automata
• Enumeration of Linear Graphs for Mappings of Finite Sets
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES

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