Tradeoffs for language recognition on alternating machines
type: Item
instance of: scholarly article
title: Tradeoffs for language recognition on alternating machines
zbMATH Open document ID: 0667.68060
DOI: 10.1016/0304-3975(89)90078-9
author: Juraj Hromkovič
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4092775
zbMATH Keywords: language recognition
zbMATH Keywords: alternating machine
zbMATH Keywords: complexity measure
zbMATH Keywords: TIME- SPACE-PARALLELISM
zbMATH Keywords: RAMS
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90078-9
OpenAlex ID: W2107702484
cites work: Q4726174
cites work: A Boolean function requiring 3n network size
cites work: Three write heads are as good ask
cites work: Q4131653
cites work: Alternation
cites work: Hierarchies of one-way multihead automata languages
cites work: An overview of computational complexity
cites work: Fooling a two way automaton or one pushdown store is better than one counter for two way machines
cites work: A time-space tradeoff for language recognition
cites work: On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
cites work: One-way simple multihead finite automata are not closed under concatenation
cites work: Q5592246
cites work: One way multihead deterministic finite automata
cites work: Q3704912
cites work: Fooling a two-way nondeterministic multihead automaton with reversal number restriction
cites work: On the power of alternation in automata theory
cites work: Q3742753
cites work: Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
cites work: On two-way multihead automata
cites work: On 3-head versus 2-head finite automata
cites work: One-way simple multihead finite automata
cites work: Alternating simple multihead finite automata
cites work: Q3048298
cites work: Alternating multihead finite automata
cites work: Q3885190
cites work: Q5545524
cites work: On time hierarchies
cites work: Q5559262
cites work: Q3690219
cites work: Q3758729
cites work: k + 1 Heads Are Better than k
cites work: On Multi-Head Finite Automata
cites work: Nondeterminism and the size of two way finite automata
cites work: Bounded-reversal multihead finite automata languages
cites work: One-way multihead writing finite automata
cites work: Q3933743
cites work: Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
cites work: An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
cites work: Q3707407
description: scientific article; zbMATH DE number 4092775