Tradeoffs for language recognition on alternating machines (Q1117697): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(89)90078-9
+Normal rank
@@ Property / OpenAlex ID @@
+W2107702484
@@ Property / OpenAlex ID: W2107702484 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4726174
@@ Property / cites work: Q4726174 / rank @@
+Normal rank
@@ Property / cites work @@
+A Boolean function requiring 3n network size
@@ Property / cites work: A Boolean function requiring 3n network size / rank @@
+Normal rank
@@ Property / cites work @@
+Three write heads are as good ask
@@ Property / cites work: Three write heads are as good ask / rank @@
+Normal rank
@@ Property / cites work @@
+Q4131653
@@ Property / cites work: Q4131653 / rank @@
+Normal rank
@@ Property / cites work @@
+Alternation
@@ Property / cites work: Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Hierarchies of one-way multihead automata languages
+Normal rank
@@ Property / cites work @@
+An overview of computational complexity
@@ Property / cites work: An overview of computational complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Fooling a two way automaton or one pushdown store is better than one counter for two way machines
+Normal rank
@@ Property / cites work @@
+A time-space tradeoff for language recognition
@@ Property / cites work: A time-space tradeoff for language recognition / rank @@
+Normal rank
@@ Property / cites work @@
+On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
+Normal rank
@@ Property / cites work @@
+One-way simple multihead finite automata are not closed under concatenation
+Normal rank
@@ Property / cites work @@
+Q5592246
@@ Property / cites work: Q5592246 / rank @@
+Normal rank
@@ Property / cites work @@
+One way multihead deterministic finite automata
@@ Property / cites work: One way multihead deterministic finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q3704912
@@ Property / cites work: Q3704912 / rank @@
+Normal rank
@@ Property / cites work @@
+Fooling a two-way nondeterministic multihead automaton with reversal number restriction
+Normal rank
@@ Property / cites work @@
+On the power of alternation in automata theory
@@ Property / cites work: On the power of alternation in automata theory / rank @@
+Normal rank
@@ Property / cites work @@
+Q3742753
@@ Property / cites work: Q3742753 / rank @@
+Normal rank
@@ Property / cites work @@
+Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
+Normal rank
@@ Property / cites work @@
+On two-way multihead automata
@@ Property / cites work: On two-way multihead automata / rank @@
+Normal rank
@@ Property / cites work @@
+On 3-head versus 2-head finite automata
@@ Property / cites work: On 3-head versus 2-head finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+One-way simple multihead finite automata
@@ Property / cites work: One-way simple multihead finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Alternating simple multihead finite automata
@@ Property / cites work: Alternating simple multihead finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q3048298
@@ Property / cites work: Q3048298 / rank @@
+Normal rank
@@ Property / cites work @@
+Alternating multihead finite automata
@@ Property / cites work: Alternating multihead finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q3885190
@@ Property / cites work: Q3885190 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5545524
@@ Property / cites work: Q5545524 / rank @@
+Normal rank
@@ Property / cites work @@
+On time hierarchies
@@ Property / cites work: On time hierarchies / rank @@
+Normal rank
@@ Property / cites work @@
+Q5559262
@@ Property / cites work: Q5559262 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3690219
@@ Property / cites work: Q3690219 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+<i>k</i>             + 1 Heads Are Better than             <i>k</i>
@@ Property / cites work: <i>k</i> + 1 Heads Are Better than <i>k</i> / rank @@
+Normal rank
@@ Property / cites work @@
+On Multi-Head Finite Automata
@@ Property / cites work: On Multi-Head Finite Automata / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterminism and the size of two way finite automata
+Normal rank
@@ Property / cites work @@
+Bounded-reversal multihead finite automata languages
+Normal rank
@@ Property / cites work @@
+One-way multihead writing finite automata
@@ Property / cites work: One-way multihead writing finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+Q3933743
@@ Property / cites work: Q3933743 / rank @@
+Normal rank
@@ Property / cites work @@
+Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
+Normal rank
@@ Property / cites work @@
+An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
+Normal rank
@@ Property / cites work @@
+Q3707407
@@ Property / cites work: Q3707407 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1117697