Reversal-Bounded Acceptors and Intersections of Linear Languages
From MaRDI portal
Publication:4044135
DOI10.1137/0203023zbMath0292.68023MaRDI QIDQ4044135
Maurice Nivat, Ronald V. Book, 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
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q04: Classical models of computation (Turing machines, etc.)
Related Items
Partial commutations and faithful rational transductions, 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, On characterisation of language families in terms of inverse morphisms, Unnamed Item, Unnamed Item, Uniform simulations of nondeterministic real time multitape turing machines, Compelled operations and operations of degreeP, Some formal results about stratificational grammars and their relevance to linguistics, Unnamed Item, Unnamed Item, On languages with a certain prefix property