Size Complexity of Two-Way Finite Automata

DOI10.1007/978-3-642-02737-6_4MaRDI QIDQ3637213zbMATH OpenOpenAlexFDO

Authors Christos Kapoutsis

Publication date 7 July 2009

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Minicomplexity
• Minicomplexity
• Minicomplexity. Some motivation, some history, and some structure (invited talk extended abstract)
• Two-way finite automata: old and recent results
• Two-way finite automata: old and recent results

Cites work

• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Alternating Pushdown and Stack Automata
• Amplification of slight probabilistic advantage at absolutely no cost in space
• An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata
• Complementing two-way finite automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Descriptional complexity of machines with limited resources
• Deterministic moles cannot solve liveness
• Finite automata and unary languages
• Finite state verifiers I
• Halting space-bounded computations
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 3568031 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2038729 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• Lower bounds on the size of sweeping automata
• Nondeterminism and the size of two way finite automata
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• On the Size Complexity of Rotating and Sweeping Automata
• Small Sweeping 2NFAs Are Not Closed Under Complement
• State-complexity of finite-state devices, state compressibility and incompressibility
• Two-way automata and length-preserving homomorphisms

Cited in

(20)

• New size hierarchies for two way automata
• Alternation in two-way finite automata
• Minicomplexity. Some motivation, some history, and some structure (invited talk extended abstract)
• Removing nondeterminism in constant height pushdown automata
• Two-way automata characterizations of L/poly versus NL
• From two-way to one-way finite automata -- three regular expression-based methods
• Minicomplexity
• On the size of two-way reasonable automata for the liveness problem
• Size complexity of rotating and sweeping automata
• An alternating hierarchy for finite automata
• On the size of two-way reasonable automata for the liveness problem
• Minicomplexity
• Two-way unary automata versus logarithmic space
• Complement for two-way alternating automata
• Probabilism versus Alternation for Automata
• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
• Power of counting by nonuniform families of polynomial-size finite automata
• Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
• Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
• Power of counting by nonuniform families of polynomial-size finite automata

This page was built for publication: Size Complexity of Two-Way Finite Automata

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