Reversal-Bounded Acceptors and Intersections of Linear Languages

DOI10.1137/0203023zbMath0292.68023OpenAlexW2055357774MaRDI QIDQ4044135

Ronald V. Book, Maurice 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

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

Related Items (18)

Some formal results about stratificational grammars and their relevance to linguistics ⋮ Unnamed Item ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ On reversal bounded alternating Turing machines ⋮ Alternating real-time computations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reset machines ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ Multiple equality sets and Post machines ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios. ⋮ Unnamed Item ⋮ On languages with a certain prefix property ⋮ On characterisation of language families in terms of inverse morphisms ⋮ Compelled operations and operations of degreeP ⋮ Improved average complexity for comparison-based sorting ⋮ On some bounded semiAFLs and AFLs ⋮ Partial commutations and faithful rational transductions

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