Parametric random generation of deterministic tree automata

DOI10.1016/J.TCS.2010.05.036MaRDI QIDQ1959655zbMATH OpenOpenAlexFDO

Authors Cyril Nicaud, Sylvain Schmitz, Pierre-Cyrille Héam

Publication date 7 October 2010

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

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

zbMATH Keywords

random generationtree automatonaverage complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Random Generation of Deterministic Tree (Walking) Automata
• Random generation of nondeterministic finite-state tree automata
• Enumeration and random generation of possibly incomplete deterministic automata
• Random generation of deterministic acyclic automata using the recursive method
• Random generation of deterministic acyclic automata using Markov chains

Cites work

• scientific article; zbMATH DE number 1408335 (Why is no real title available?)
• Antichain-Based Universality and Inclusion Testing over Nondeterministic Finite Tree Automata
• Antichains: A New Algorithm for Checking Universality of Finite Automata
• Büchi complementation made tight
• Enumeration and random generation of accessible automata
• Enumeration and random generation of possibly incomplete deterministic automata
• Experimental Evaluation of Classical Automata Constructions
• Five Determinisation Algorithms
• Learning Minimal Separating DFA’s for Compositional Verification
• On the average complexity of Moore's state minimization algorithm
• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Random generation of DFAs
• Transitive closure logic, nested tree walking automata, and XPath
• Tree-Walking Automata Do Not Recognize All Regular Languages
• Uniform random generation of decomposable structures using floating-point arithmetic
• Visibly pushdown languages

Cited in

(7)

• From tree automata to string automata minimization
• Sampling different kinds of acyclic automata using Markov chains
• Random generation of nondeterministic finite-state tree automata
• Random Generation of Deterministic Tree (Walking) Automata
• Random generation and enumeration of accessible deterministic real-time pushdown automata
• Random generation of deterministic acyclic automata using Markov chains
• Random generation of DFAs

Describes a project that uses

Uses Software

• Antichains
• REGAL

This page was built for publication: Parametric random generation of deterministic tree automata

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