Two-Way Unary Automata versus Logarithmic Space

DOI10.1007/978-3-642-14455-4_19MaRDI QIDQ3584893zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Viliam Geffert, Giovanni Pighizzini

Publication date 31 August 2010

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

Full work available at URL https://doi.org/10.1007/978-3-642-14455-4_19

zbMATH Keywords

finite automatalogarithmic spacespace complexitystate complexityunary regular languages

Mathematics Subject Classification ID

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

Recommendations

• Two-way unary automata versus logarithmic space
• Two-way automata versus logarithmic space
• Two-Way Automata versus Logarithmic Space
• scientific article; zbMATH DE number 1502111
• Two-Way Non-Uniform Finite Automata
• Two-way non-uniform finite automata
• scientific article; zbMATH DE number 1848284
• State complexity of operations on two-way finite automata over a unary alphabet
• Unary Languages Recognized by Two-Way One-Counter Automata
• On the transformation of two-way deterministic finite automata to unambiguous finite automata

Cited in

(6)

• Two-way automata versus logarithmic space
• Two-way automata characterizations of L/poly versus NL
• Two-Way Automata versus Logarithmic Space
• Nondeterminism is essential in small 2FAs with few reversals
• scientific article; zbMATH DE number 1848284 (Why is no real title available?)
• Two-way unary automata versus logarithmic space

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

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