scientific article; zbMATH DE number 79114

MaRDI QIDQ4016418zbMATH OpenFDO

Authors Juraj Hromkovič

Publication date 14 December 1992

Full work available at URL https://eudml.org/doc/31849

zbMATH Keywords

alternationlower boundtradeoff of complexity measures

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Tradeoffs for language recognition on alternating machines
• scientific article; zbMATH DE number 3956444
• scientific article; zbMATH DE number 4007730
• Lower bounds for language recognition on two-dimensional alternating multihead machines
• Sublogarithmic Bounds on Space and Reversals

Cites work

• k + 1 Heads Are Better than k
• A time-space tradeoff for language recognition
• Alternating simple multihead finite automata
• Alternation
• Bounded-reversal multihead finite automata languages
• Fooling a two-way nondeterministic multihead automaton with reversal number restriction
• scientific article; zbMATH DE number 3642749 (Why is no real title available?)
• scientific article; zbMATH DE number 3738947 (Why is no real title available?)
• On the power of alternation in automata theory
• One way multihead deterministic finite automata
• Tradeoffs for language recognition on alternating machines

Cited in

(8)

• Tradeoffs for language recognition on alternating machines
• Lower bounds for language recognition on two-dimensional alternating multihead machines
• Information cost tradeoffs for augmented index and streaming language recognition
• A time-space tradeoff for language recognition
• scientific article; zbMATH DE number 3926273 (Why is no real title available?)
• scientific article; zbMATH DE number 3956444 (Why is no real title available?)
• scientific article; zbMATH DE number 4007730 (Why is no real title available?)
• PARALLELIZING GRAMMATICAL FUNCTIONS: P600 AND P345 REFLECT DIFFERENT COST OF REANALYSIS

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4016418)