Tradeoffs for language recognition on alternating machines
From MaRDI portal
DOI10.1016/0304-3975(89)90078-9zbMATH Open0667.68060OpenAlexW2107702484MaRDI QIDQ1117697FDOQ1117697
Authors: Juraj Hromkovič 
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90078-9
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Alternation
- On Multi-Head Finite Automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Boolean function requiring 3n network size
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- Title not available (Why is that?)
- An overview of computational complexity
- Nondeterminism and the size of two way finite automata
- Alternating multihead finite automata
- Hierarchies of one-way multihead automata languages
- k + 1 Heads Are Better than k
- Bounded-reversal multihead finite automata languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fooling a two-way nondeterministic multihead automaton with reversal number restriction
- On 3-head versus 2-head finite automata
- Title not available (Why is that?)
- On two-way multihead automata
- Title not available (Why is that?)
- One way multihead deterministic finite automata
- One-way multihead writing finite automata
- On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
- One-way simple multihead finite automata are not closed under concatenation
- On time hierarchies
- One-way simple multihead finite automata
- Fooling a two way automaton or one pushdown store is better than one counter for two way machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- Alternating simple multihead finite automata
- On the power of alternation in automata theory
- A time-space tradeoff for language recognition
- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- Title not available (Why is that?)
- Three write heads are as good ask
- Title not available (Why is that?)
Cited In (13)
- Lifting query complexity to time-space complexity for two-way finite automata
- Title not available (Why is that?)
- Information cost tradeoffs for augmented index and streaming language recognition
- On the power of synchronization in parallel computations
- Some properties of space-bounded synchronized alternating Turing machines with universal states only
- Communication for alternating machines
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- A time-space tradeoff for language recognition
- Title not available (Why is that?)
- Lower bounds for language recognition on two-dimensional alternating multihead machines
- The Communication Hierarchy of Time and Space Bounded Parallel Machines
- On problems for which no oracle can help
- On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
This page was built for publication: Tradeoffs for language recognition on alternating machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117697)
