Two-Way Automata versus Logarithmic Space

DOI10.1007/978-3-642-20712-9_28MaRDI QIDQ3007639zbMATH OpenOpenAlexFDO

Authors Christos Kapoutsis

Publication date 17 June 2011

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20712-9_28

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Two-way automata versus logarithmic space
• Two-way unary automata versus logarithmic space
• Two-Way Unary Automata versus Logarithmic Space
• Two-way automata and length-preserving homomorphisms
• Two-way automaton computations
• Two-way finite automata: old and recent results
• Two-way finite automata: old and recent results
• Two-way automata over locally finite semirings
• scientific article; zbMATH DE number 512810
• scientific article; zbMATH DE number 177806

Cites work

• Classes of languages and linear-bounded automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Deterministic moles cannot solve liveness
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3917711 (Why is no real title available?)
• scientific article; zbMATH DE number 3568031 (Why is no real title available?)
• scientific article; zbMATH DE number 2038729 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Lower bounds on the size of sweeping automata
• Nondeterminism and the size of two way finite automata
• Relationships between nondeterministic and deterministic tape complexities
• Some Results on Tape-Bounded Turing Machines
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• Two-Way Unary Automata versus Logarithmic Space

Cited in

(13)

• New size hierarchies for two way automata
• On the size of logical automata
• Oblivious two-way finite automata: decidability and complexity
• Two-way automata versus logarithmic space
• Two-way automata characterizations of L/poly versus NL
• A logical characterization of small 2NFAs
• Two-Way Automata Characterizations of L/poly versus NL
• Nondeterminism is essential in small 2FAs with few reversals
• Two-Way Unary Automata versus Logarithmic Space
• A logical characterization of small 2NFAs
• On the state complexity of operations on two-way finite automata
• Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
• Two-way unary automata versus logarithmic space

This page was built for publication: Two-Way Automata versus Logarithmic Space

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