New results on the minimum amount of useful space

DOI10.1142/S0129054116400098MaRDI QIDQ2814840zbMATH OpenOpenAlexFDO

Authors Zuzana Bednárová, Viliam Geffert, Klaus Reinhardt, Abuzer Yakaryılmaz

Publication date 23 June 2016

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2892

zbMATH Keywords

nondeterminismpushdown automataquantum computationunary languagesalternationcounter automatanonregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak $loglogn$ space, (ii) $loglogn$ is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak $logn$ space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong $loglogn$ space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum and classical states with middle $logn$ space and bounded error.

Recommendations

• The minimum amount of useful space: new results and new directions
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• Minimal useful size of counters for (real-time) multicounter automata
• Minimal Size of Counters for (Real-Time) Multicounter Automata
• scientific article; zbMATH DE number 3917711

Cites work

• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• A tree-height hierarchy of context-free languages
• Alternation
• An optimal lower bound for nonregular languages
• Efficient probability amplification in two-way quantum finite automata
• On Chebyshev-Type Inequalities for Primes
• On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
• One-counter verifiers for decidable languages
• Quantum finite automata: a modern introduction
• Space bounds for processing contentless inputs
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Superiority of one-way and realtime quantum machines
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• The minimum amount of useful space: new results and new directions
• Two-way finite automata with quantum and classical states.

Cited in

(12)

• scientific article; zbMATH DE number 7104930 (Why is no real title available?)
• Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
• Uncountable classical and quantum complexity classes
• scientific article; zbMATH DE number 3917711 (Why is no real title available?)
• The minimum amount of useful space: new results and new directions
• Pushdown and one-counter automata: constant and non-constant memory usage
• Minimal useful size of counters for (real-time) multicounter automata
• Minimal Size of Counters for (Real-Time) Multicounter Automata
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Pushdown automata and constant height: decidability and bounds
• scientific article; zbMATH DE number 18635 (Why is no real title available?)
• Push complexity: optimal bounds and unary inputs

This page was built for publication: New results on the minimum amount of useful space

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