Language recognition by marking automata

DOI10.1016/S0019-9958(72)90205-7MaRDI QIDQ5653562zbMATH OpenFDO

Authors R. W. Ritchie, Frederick Neil Springsteel

Publication date 1972

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(72)90205-7

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Formal languages and automata (68Q45)

Cited in

(17)

• On pebble automata
• Some subclasses of context-free languages in NC^ 1
• On the relative complexity of some languages in \(NC^ 1\)
• On the time and tape complexity of weak unification
• 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
• On the descriptional power of heads, counters, and pebbles
• Some properties of one-pebble Turing machines with sublogarithmic space
• A combinatorial characterization of smooth LTCs and applications
• scientific article; zbMATH DE number 3551931 (Why is no real title available?)
• The equivalence of pebbles and sensing heads for finite automata
• Dynamic algorithms for the Dyck languages
• Stateless one-way multi-head finite automata with pebbles
• Complexity of multi-head finite automata: origins and directions
• Some classes of languages in \(NC^ 1\)

This page was built for publication: Language recognition by marking automata

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