ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE

DOI10.1142/S0129054192000073MaRDI QIDQ4020282zbMATH OpenFDO

Authors Juraj Hromkovič, Branislav Rovan, Anna Slobodová, Itsuo Takanami, Katsushi Inoue, K. W. Wagner

Publication date 16 January 1993

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

context-sensitive languagessynchronized alternationmultihead finite automatasynchronization complexityone-way synchronized alternating finite automataone-way synchronized Turing machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4213434
• On space-bounded synchronized alternating Turing machines
• ON THE POWER OF ONE-WAY GLOBALLY DETERMINISTIC SYNCHRONIZED ALTERNATING TURING MACHINES AND MULTIHEAD AUTOMATA
• On the power of synchronization in parallel computations
• Some properties of space-bounded synchronized alternating Turing machines with universal states only

Cited in

(13)

• scientific article; zbMATH DE number 17800 (Why is no real title available?)
• A communication hierarchy of parallel computations
• Some properties of space-bounded synchronized alternating Turing machines with universal states only
• Communication for alternating machines
• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• New results concerning synchronized finite automata
• Four-dimensional synchronized alternating Turing machines
• Alternating finite automata and star-free languages
• On communication-bounded synchronized alternating finite automata
• scientific article; zbMATH DE number 4060723 (Why is no real title available?)
• On space-bounded synchronized alternating Turing machines
• A note on realtime one-way synchronized alternating one-counter automata
• scientific article; zbMATH DE number 1696661 (Why is no real title available?)

This page was built for publication: ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE

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