Advertisement
Published in:
2010 | OriginalPaper | Chapter
On Lookahead Hierarchies for Monotone and Deterministic Restarting Automata with Auxiliary Symbols (Extended Abstract)
Author : Natalie Schluter
Published in: Developments in Language Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A restarting automaton is a special type of linearly bounded automaton with fixed lookahead length
k
, whose computation proceeds in cycles performing one length-reducing rewrite of the lookahead contents per cycle as the only modification of the input. Through various restrictions on this machine model, a vast number of traditional and new language classes have been excavated. In two studies on lookahead hierarchies for restarting automata without auxiliary symbols [2,3], it was shown that lookahead length is often a significant restriction on the power of these types of restarting automata. No similar study on lookahead hierarchies for restarting automata with auxiliary symbols has been explicitly carried out.