Self-Verifying Finite Automata and Descriptional Complexity

DOI10.1007/978-3-319-41114-9_3zbMath1476.68131OpenAlexW2482365960MaRDI QIDQ2829967

Galina Jirásková

Publication date: 9 November 2016

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01633958/file/416473_1_En_3_Chapter.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversal of binary regular languages
• Optimal simulation of self-verifying automata by deterministic automata
• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• State complexity of some operations on binary regular languages
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Kleene Star on Unary Regular Languages
• Operations on Self-Verifying Finite Automata
• Nondeterminism and the size of two way finite automata
• An upper bound for transforming self-verifying automata into deterministic ones
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On cliques in graphs

This page was built for publication: Self-Verifying Finite Automata and Descriptional Complexity