Optimal simulation of self-verifying automata by deterministic automata
From MaRDI portal
Publication:553320
DOI10.1016/j.ic.2010.11.017zbMath1217.68132WikidataQ57380749 ScholiaQ57380749MaRDI QIDQ553320
Galina Jirásková, Giovanni Pighizzini
Publication date: 27 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2010.11.017
Related Items
Unnamed Item, Self-Verifying Pushdown and Queue Automata, Nondeterministic Moore Automata and Brzozowski’s Algorithm, Descriptional Complexity of the Forever Operator, Iterative arrays with self-verifying communication cell, Self-verifying Cellular Automata, Descriptional Complexity of Non-Unary Self-Verifying Symmetric Difference Automata, Nondeterministic Moore automata and Brzozowski's minimization algorithm, Reversal of binary regular languages, Optimal state reductions of automata with partially specified behaviors, Iterative arrays with self-verifying communication cell, Self-Verifying Finite Automata and Descriptional Complexity, Unary Self-verifying Symmetric Difference Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite automata and unary languages
- Complementing unary nondeterministic automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata
- Nondeterministic Communication with a Limited Number of Advice Bits
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- 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
- On cliques in graphs
