Reversal-Bounded Acceptors and Intersections of Linear Languages

DOI10.1137/0203023MaRDI QIDQ4044135zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, M. Nivat, Michael S. Paterson

Publication date 1975

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0203023

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3845055
• scientific article; zbMATH DE number 3885308
• A note on bounded-reversal multipushdown machines
• Pushdown automata with reversal-bounded counters
• One-reversal counter machines and multihead automata: revisited

Cited in

(18)

• Representations of language families by homomorphic equality operations and generalized equality sets
• On reversal bounded alternating Turing machines
• Alternating real-time computations
• Reset machines
• Multiple equality sets and Post machines
• Refining the hierarchy of blind multicounter languages and twist-closed trios.
• On some bounded semiAFLs and AFLs
• scientific article; zbMATH DE number 3845055 (Why is no real title available?)
• On characterisation of language families in terms of inverse morphisms
• scientific article; zbMATH DE number 3808971 (Why is no real title available?)
• Uniform simulations of nondeterministic real time multitape turing machines
• scientific article; zbMATH DE number 3677223 (Why is no real title available?)
• Compelled operations and operations of degreeP
• Some formal results about stratificational grammars and their relevance to linguistics
• scientific article; zbMATH DE number 3551931 (Why is no real title available?)
• On languages with a certain prefix property
• scientific article; zbMATH DE number 3604381 (Why is no real title available?)
• Partial commutations and faithful rational transductions

This page was built for publication: Reversal-Bounded Acceptors and Intersections of Linear Languages

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