Language recognition by marking automata
From MaRDI portal
Publication:5653562
DOI10.1016/S0019-9958(72)90205-7zbMath0242.68032MaRDI QIDQ5653562
R. W. Ritchie, Frederick Neil Springsteel
Publication date: 1972
Published in: Information and Control (Search for Journal in Brave)
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)
Related Items (17)
On pebble automata ⋮ The equivalence of pebbles and sensing heads for finite automata ⋮ Unnamed Item ⋮ Dynamic algorithms for the Dyck languages ⋮ Some subclasses of context-free languages in \(NC^ 1\) ⋮ On the relative complexity of some languages in \(NC^ 1\) ⋮ Complexity of multi-head finite automata: origins and directions ⋮ On the time and tape complexity of weak unification ⋮ On the descriptional power of heads, counters, and pebbles ⋮ On the pre-AFL of \([lg\;n\) space and related families of languages] ⋮ Marker automata ⋮ Stack languages and log n space ⋮ Lower bounds on space complexity for contextfree recognition ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Some classes of languages in \(NC^ 1\) ⋮ Some properties of one-pebble Turing machines with sublogarithmic space ⋮ STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES
This page was built for publication: Language recognition by marking automata
