An upper bound for transforming self-verifying automata into deterministic ones

DOI10.1051/ita:2007017zbMath1130.68067OpenAlexW2028979408MaRDI QIDQ5425747

Sebastian Seibert, Ira Assent

Publication date: 14 November 2007

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2007__41_3_261_0

zbMATH Keywords

descriptional complexitypower set constructionself-verifying nondeterministic automata

Mathematics Subject Classification ID

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

Related Items

Descriptional Complexity of Non-Unary Self-Verifying Symmetric Difference Automata ⋮ Unnamed Item ⋮ Optimal simulation of self-verifying automata by deterministic automata ⋮ Converting Self-verifying Automata into Deterministic Automata ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Unary Self-verifying Symmetric Difference Automata

Cites Work

• Unnamed Item
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata