More on deterministic and nondeterministic finite cover automata

DOI10.1016/j.tcs.2016.10.006zbMath1371.68149OpenAlexW2537940722MaRDI QIDQ2357103

Markus Holzer, Hermann Gruber, Sebastian Jakobi

Publication date: 19 June 2017

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

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

zbMATH Keywords

finite languageslower bound techniques(nondeterministic) cover automataaverage state complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• A lower bound technique for the size of nondeterministic finite automata
• Incremental construction of minimal deterministic finite cover automata
• A maxmin problem on finite automata
• Intersection and union of regular languages and state complexity
• On the average state and transition complexity of finite languages
• Minimizing nfa's and regular expressions
• AN EFFICIENT ALGORITHM FOR CONSTRUCTING MINIMAL COVER AUTOMATA FOR FINITE LANGUAGES
• THE AVERAGE STATE COMPLEXITY OF RATIONAL OPERATIONS ON FINITE LANGUAGES
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Non-Deterministic Finite Cover Automata
• Similarity relations and cover automata
• Computing All ℓ-Cover Automata Fast
• FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• A TIME AND SPACE EFFICIENT ALGORITHM FOR MINIMIZING COVER AUTOMATA FOR FINITE LANGUAGES
• Minimal cover-automata for finite languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item