Parametric random generation of deterministic tree automata

DOI10.1016/j.tcs.2010.05.036zbMath1209.68298OpenAlexW2066694987MaRDI QIDQ1959655

Sylvain Schmitz, Cyril Nicaud, 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

average complexityrandom generationtree automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (4)

Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata ⋮ Sampling different kinds of acyclic automata using Markov chains ⋮ From tree automata to string automata minimization ⋮ Random Generation of Deterministic Acyclic Automata Using Markov Chains

Uses Software

• REGAL
• Antichains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumeration and random generation of accessible automata
• Uniform random generation of decomposable structures using floating-point arithmetic
• Random generation of DFAs
• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Transitive closure logic, nested tree walking automata, and XPath
• Visibly pushdown languages
• Antichain-Based Universality and Inclusion Testing over Nondeterministic Finite Tree Automata
• Five Determinisation Algorithms
• Learning Minimal Separating DFA’s for Compositional Verification
• Tree-Walking Automata Do Not Recognize All Regular Languages
• Experimental Evaluation of Classical Automata Constructions
• Büchi Complementation Made Tight
• Antichains: A New Algorithm for Checking Universality of Finite Automata

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