Tradeoffs for language recognition on alternating machines
From MaRDI portal
(Redirected from Publication:1117697)
Recommendations
Cites work
- scientific article; zbMATH DE number 3642749 (Why is no real title available?)
- scientific article; zbMATH DE number 3913677 (Why is no real title available?)
- scientific article; zbMATH DE number 3932419 (Why is no real title available?)
- scientific article; zbMATH DE number 3936518 (Why is no real title available?)
- scientific article; zbMATH DE number 3978428 (Why is no real title available?)
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 3690693 (Why is no real title available?)
- scientific article; zbMATH DE number 3750291 (Why is no real title available?)
- scientific article; zbMATH DE number 3560742 (Why is no real title available?)
- scientific article; zbMATH DE number 3999837 (Why is no real title available?)
- scientific article; zbMATH DE number 3257409 (Why is no real title available?)
- scientific article; zbMATH DE number 3275600 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- k + 1 Heads Are Better than k
- A Boolean function requiring 3n network size
- A time-space tradeoff for language recognition
- Alternating multihead finite automata
- Alternating simple multihead finite automata
- Alternation
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- An overview of computational complexity
- Bounded-reversal multihead finite automata languages
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- Fooling a two way automaton or one pushdown store is better than one counter for two way machines
- Fooling a two-way nondeterministic multihead automaton with reversal number restriction
- Hierarchies of one-way multihead automata languages
- Nondeterminism and the size of two way finite automata
- On 3-head versus 2-head finite automata
- On Multi-Head Finite Automata
- On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
- On the power of alternation in automata theory
- On time hierarchies
- On two-way multihead automata
- One way multihead deterministic finite automata
- One-way multihead writing finite automata
- One-way simple multihead finite automata
- One-way simple multihead finite automata are not closed under concatenation
- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- Three write heads are as good ask
Cited in
(13)- Communication for alternating machines
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- scientific article; zbMATH DE number 79114 (Why is no real title available?)
- Lifting query complexity to time-space complexity for two-way finite automata
- On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
- A time-space tradeoff for language recognition
- Lower bounds for language recognition on two-dimensional alternating multihead machines
- Information cost tradeoffs for augmented index and streaming language recognition
- The Communication Hierarchy of Time and Space Bounded Parallel Machines
- On the power of synchronization in parallel computations
- scientific article; zbMATH DE number 3956444 (Why is no real title available?)
- On problems for which no oracle can help
- Some properties of space-bounded synchronized alternating Turing machines with universal states only
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)
