{\text{ASPACE}}(o(\log \log n)) is Regular
From MaRDI portal
Publication:4037689
Recommendations
- scientific article; zbMATH DE number 3917711
- The Sublogarithmic Alternating Space World
- Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
- A remark on middle space bounded alternating Turing machines
- Alternating on-line Turing machines with only universal states and small space bounds
Cited in
(20)- A communication hierarchy of parallel computations
- Bridging across the (n) space frontier
- The alternation hierarchy for sublogarithmic space is infinite
- A remark on middle space bounded alternating Turing machines
- For completeness, sublogarithmic space is no space.
- A space lower bound for acceptance by one-way _2-alternating machines
- New results on the minimum amount of useful space
- Alternating demon space is closed under complement and other simulations for sublogarithmic space
- scientific article; zbMATH DE number 3883610 (Why is no real title available?)
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- Factoring and Testing Primes in Small Space
- scientific article; zbMATH DE number 3917711 (Why is no real title available?)
- A hierarchy that does not collapse : alternations in low level space
- An alternating hierarchy for finite automata
- Alternating space is closed under complement and other simulations for sublogarithmic space
- Minimal Size of Counters for (Real-Time) Multicounter Automata
- Closure property of probabilistic Turing machines and alternating Turing machines with sublogarithmic spaces
- Unary coded NP-complete languages in \(\mathrm{ASpace}(\log \log n)\)
- scientific article; zbMATH DE number 7539923 (Why is no real title available?)
- Time lower bounds do not exist for CRCW PRAMs
This page was built for publication: ${\text{ASPACE}}(o(\log \log n))$ is Regular
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4037689)
