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)

Mathematics Subject Classification ID

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

Cited in

(17)

• The equivalence of pebbles and sensing heads for finite automata
• On the pre-AFL of \([lg\;n]\) space and related families of languages
• Marker automata
• Some properties of one-pebble Turing machines with sublogarithmic space
• Some subclasses of context-free languages in \(NC^ 1\)
• scientific article; zbMATH DE number 3551931 (Why is no real title available?)
• A combinatorial characterization of smooth LTCs and applications
• Some classes of languages in \(NC^ 1\)
• Complexity of multi-head finite automata: origins and directions
• On pebble automata
• On the relative complexity of some languages in \(NC^ 1\)
• Stack languages and log n space
• Lower bounds on space complexity for contextfree recognition
• On the time and tape complexity of weak unification
• Stateless one-way multi-head finite automata with pebbles
• On the descriptional power of heads, counters, and pebbles
• Dynamic algorithms for the Dyck languages

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)