New Results on the Minimum Amount of Useful Space
From MaRDI portal
Publication:2814840
DOI10.1142/S0129054116400098zbMath1338.68138arXiv1405.2892OpenAlexW2962749334MaRDI QIDQ2814840
Viliam Geffert, Klaus Reinhardt, Zuzana Bednárová, 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
quantum computationnondeterminismalternationpushdown automataunary languagescounter automatanonregular languages
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
Uncountable realtime probabilistic classes ⋮ Unnamed Item ⋮ Pushdown and one-counter automata: constant and non-constant memory usage ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Pushdown automata and constant height: decidability and bounds ⋮ Uncountable classical and quantum complexity classes
Cites Work
- Efficient probability amplification in two-way quantum finite automata
- Space bounds for processing contentless inputs
- An optimal lower bound for nonregular languages
- Two-way finite automata with quantum and classical states.
- The Minimum Amount of Useful Space: New Results and New Directions
- Quantum Finite Automata: A Modern Introduction
- A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
- Alternation
- On Chebyshev-Type Inequalities for Primes
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- Superiority of one-way and realtime quantum machines
- One-Counter Verifiers for Decidable Languages
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
This page was built for publication: New Results on the Minimum Amount of Useful Space
