Alternating on-line Turing machines with only universal states and small space bounds
Let \({\mathcal L}[AONTM(L(n))]\) be the class of sets accepted by L(n) space bounded alternating on-line Turing machines, and \({\mathcal L}[UONTM(L(n))]\) be the class of sets accepted by L(n) space bounded alternating on-line Turing machines with only universal states. This note first shows that, for any L(n) such that L(n)\(\geq \log \log n\) and \(\lim_{n\to \infty}[L(n)/\log n]=0\), (i) \({\mathcal L}[UONTM(L(n))]\subseteq {\mathcal L}[AONTM(L(n))]\), (ii) \({\mathcal L}[UONTM(L(n))]\) is not closed under complementation, and (iii) \({\mathcal L}[UONTM(L(n))]\) is properly contained in the class of sets accepted by L(n) space bounded alternating Turing machines with only universal states. We then show that there exists an infinite hierarchy among \({\mathcal L}[UONTM(L(n))]'s\) with log log \(n\leq L(n)\leq \log n\).
- Some observations concerning alternating Turing machines using small space
- The alternation hierarchy for sublogarithmic space is infinite
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- The Sublogarithmic Alternating Space World
- Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
- A note on alternating on-line Turing machines
- Alternation
- An extension of Savitch's theorem to small space bounds
- Bandwidth constraints on problems complete for polynomial time
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- On alternation
- On tape-bounded complexity classes and multihead finite automata
- Tree-size bounded alternation
- Two-dimensional alternating turing machines with only universal states
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- Some observations concerning alternating Turing machines using small space
- Some properties of space-bounded synchronized alternating Turing machines with universal states only
- On space-bounded synchronized alternating Turing machines
- On 1-inkdot alternating Turing machines with small space
- ${\text{ASPACE}}(o(\log \log n))$ is Regular
- Alternation for sublogarithmic space-bounded alternating pushdown automata
- A note on alternating on-line Turing machines
This page was built for publication: Alternating on-line Turing machines with only universal states and small space bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083207)
