${\text{ASPACE}}(o(\log \log n))$ is Regular
From MaRDI portal
Publication:4037689
DOI10.1137/0222011zbMath0767.68039OpenAlexW150474545MaRDI QIDQ4037689
Publication date: 16 May 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222011
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (18)
A remark on middle space bounded alternating Turing machines ⋮ A communication hierarchy of parallel computations ⋮ An alternating hierarchy for finite automata ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ Time lower bounds do not exist for CRCW PRAMs ⋮ Minimal Size of Counters for (Real-Time) Multicounter Automata ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Factoring and Testing Primes in Small Space ⋮ Improved average complexity for comparison-based sorting ⋮ New Results on the Minimum Amount of Useful Space ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space ⋮ Bridging across the \(\log(n)\) space frontier ⋮ UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n) ⋮ CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES ⋮ For completeness, sublogarithmic space is no space. ⋮ The alternation hierarchy for sublogarithmic space is infinite
This page was built for publication: ${\text{ASPACE}}(o(\log \log n))$ is Regular
