Language recognition by marking automata

DOI10.1016/S0019-9958(72)90205-7zbMATH Open0242.68032MaRDI QIDQ5653562FDOQ5653562

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)

• Stack languages and log n space
• Some subclasses of context-free languages in \(NC^ 1\)
• The equivalence of pebbles and sensing heads for finite automata
• On pebble automata
• Complexity of multi-head finite automata: origins and directions
• On the relative complexity of some languages in \(NC^ 1\)
• On the time and tape complexity of weak unification
• Some classes of languages in \(NC^ 1\)
• Some properties of one-pebble Turing machines with sublogarithmic space
• A combinatorial characterization of smooth LTCs and applications
• Lower bounds on space complexity for contextfree recognition
• On the descriptional power of heads, counters, and pebbles
• Dynamic algorithms for the Dyck languages
• STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES
• Title not available (Why is that?)
• On the pre-AFL of \([lg\;n]\) space and related families of languages
• Marker automata

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)