Optimal simulation of self-verifying automata by deterministic automata

DOI10.1016/J.IC.2010.11.017MaRDI QIDQ553320zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

zbMATH Keywords

descriptional complexityfinite automatanondeterminismself-verifying automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Recommendations

• Converting Self-verifying Automata into Deterministic Automata
• Self-verifying finite automata and descriptional complexity
• scientific article; zbMATH DE number 7444008
• Operations on Self-Verifying Finite Automata
• Unary Self-verifying Symmetric Difference Automata

Cites work

• scientific article; zbMATH DE number 1502109 (Why is no real title available?)
• scientific article; zbMATH DE number 1747444 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3269886 (Why is no real title available?)
• An upper bound for transforming self-verifying automata into deterministic ones
• Complementing unary nondeterministic automata
• Descriptional complexity of machines with limited resources
• Finite automata and unary languages
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• Nondeterministic Communication with a Limited Number of Advice Bits
• On cliques in graphs
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite 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

Cited in

(18)

• Reversal of binary regular languages
• scientific article; zbMATH DE number 3305070 (Why is no real title available?)
• Self-verifying pushdown and queue automata
• An upper bound for transforming self-verifying automata into deterministic ones
• Converting Self-verifying Automata into Deterministic Automata
• Descriptional Complexity of Non-Unary Self-Verifying Symmetric Difference Automata
• Self-verifying Cellular Automata
• Nondeterministic Moore automata and Brzozowski's minimization algorithm
• Descriptional complexity of the forever operator
• Optimal state reductions of automata with partially specified behaviors
• Self-verifying finite automata and descriptional complexity
• Iterative arrays with self-verifying communication cell
• Unary Self-verifying Symmetric Difference Automata
• Optimal simulations between unary automata
• scientific article; zbMATH DE number 7444008 (Why is no real title available?)
• Nondeterministic Moore automata and Brzozowski's algorithm
• Self-verifying cellular automata
• Iterative arrays with self-verifying communication cell

This page was built for publication: Optimal simulation of self-verifying automata by deterministic automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q553320)