scientific article; zbMATH DE number 3956444

MaRDI QIDQ3725549zbMATH OpenFDO

Authors Juraj Hromkovič

Publication date 1986

zbMATH Keywords

alternating machinealternationcomplexity measureslower boundsmultihead machines and automatasequential and parallel computationstradeoffs of

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Tradeoffs for language recognition on alternating machines
• Lower bounds for language recognition on two-dimensional alternating multihead machines
• scientific article; zbMATH DE number 79114
• Multihead one-way finite automata
• A time-space tradeoff for language recognition

Cited in

(9)

• Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs
• 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
• Parallel learning of automatic classes of languages
• A time-space tradeoff for language recognition
• scientific article; zbMATH DE number 3926273 (Why is no real title available?)
• scientific article; zbMATH DE number 79114 (Why is no real title available?)
• Separation of deterministic, nondeterministic and alternating complexity classes

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 Q3725549)