Determinism vs. nondeterminism for two-way automata. Representing the meaning of states by logical formulæ

DOI10.1007/978-3-642-31653-1_4zbMATH Open1358.68170OpenAlexW2279174953MaRDI QIDQ3167481FDOQ3167481

Richard Štefanec, Richard Královič, Rastislav Královič, Juraj Hromkovič

Publication date: 2 November 2012

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31653-1_4

Recommendations

• Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
• On the size of logical automata
• On the size of two-way reasonable automata for the liveness problem
• Two-way automata versus logarithmic space
• On the size of two-way reasonable automata for the liveness problem

zbMATH Keywords

nondeterminismstate complexitytwo-way finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Determinism vs. nondeterminism for two-way automata. Representing the meaning of states by logical formulæ

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