Affordable Access

Publisher Website

Restarting automata with restricted utilization of auxiliary symbols

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
363
Issue
2
Identifiers
DOI: 10.1016/j.tcs.2006.07.023
Keywords
  • Restarting Automaton
  • Auxiliary Symbol
  • [Formula Omitted]-Linear Language
Disciplines
  • Linguistics

Abstract

Abstract The restarting automaton is a restricted model of computation that was introduced by Jančar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyse sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

There are no comments yet on this publication. Be the first to share your thoughts.