Optimal simulation of self-verifying automata by deterministic automata
From MaRDI portal
Publication:553320
DOI10.1016/j.ic.2010.11.017zbMath1217.68132OpenAlexW1978638999WikidataQ57380749 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 (13)
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 ⋮ Unnamed Item ⋮ Descriptional Complexity of the Forever Operator ⋮ Self-Verifying Pushdown and Queue Automata ⋮ Iterative arrays with self-verifying communication cell ⋮ Iterative arrays with self-verifying communication cell ⋮ Nondeterministic Moore Automata and Brzozowski’s Algorithm ⋮ Optimal state reductions of automata with partially specified behaviors ⋮ 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
This page was built for publication: Optimal simulation of self-verifying automata by deterministic automata
