Minicomplexity

DOI10.25596/JALC-2012-205zbMATH Open1322.68123MaRDI QIDQ5178455FDOQ5178455

Authors: Christos Kapoutsis 

Publication date: 16 March 2015

Recommendations

• Minicomplexity
• Minicomplexity. Some motivation, some history, and some structure (invited talk extended abstract)
• Size Complexity of Two-Way Finite Automata
• Two-way finite automata: old and recent results
• On the State Complexity of Operations on Two-Way Finite Automata

zbMATH Keywords

descriptional complexityspace complexityTuring machinesstate complexitytwo-way finite automataminicomplexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (12)

• Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
• A logical characterization of small 2NFAs
• A logical characterization of small 2NFAs
• Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
• Improved complement for two-way alternating automata
• Minicomplexity
• Complement for two-way alternating automata
• Two-way non-uniform finite automata
• Two-Way Non-Uniform Finite Automata
• Size Complexity of Two-Way Finite Automata
• Power of counting by nonuniform families of polynomial-size finite automata
• Minicomplexity. Some motivation, some history, and some structure (invited talk extended abstract)

This page was built for publication: Minicomplexity

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