New results on the minimum amount of useful space

DOI10.1142/S0129054116400098zbMATH Open1338.68138arXiv1405.2892OpenAlexW2962749334MaRDI QIDQ2814840FDOQ2814840

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)

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.

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

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

zbMATH Keywords

nondeterminismpushdown automataquantum computationunary languagesalternationcounter automatanonregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (12)

• Title not available (Why is that?)
• Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
• Uncountable classical and quantum complexity classes
• Title not available (Why is that?)
• 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
• Push complexity: optimal bounds and unary inputs
• Title not available (Why is that?)

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)