Preprint
Restarting automata with restricted utilization of auxiliary symbols
Abstract
The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze 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.
Citation
@article{urn:nbn:de:hebis:34-200604048993,
author={Jurdzinski, Tomasz and Otto, Friedrich},
title={Restarting automata with restricted utilization of auxiliary symbols},
year={2005}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2005$n2005 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-200604048993 3000 Jurdzinski, Tomasz 3010 Otto, Friedrich 4000 Restarting automata with restricted utilization of auxiliary symbols / Jurdzinski, Tomasz 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-200604048993=x R 4204 \$dPreprint 4170 Mathematische Schriften Kassel 7136 ##0##urn:nbn:de:hebis:34-200604048993
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2006-04-04T12:38:45Z 2006-04-04T12:38:45Z 2005 urn:nbn:de:hebis:34-200604048993 http://hdl.handle.net/123456789/200604048993 256102 bytes application/pdf eng Universität Kassel, FB 17, Mathematik/Informatik Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Restarting automation Descriptional complexity Auxiliary symbol 004 Restarting automata with restricted utilization of auxiliary symbols Preprint The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze 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. open access Jurdzinski, Tomasz Otto, Friedrich Mathematische Schriften Kassel 05, 02 Mathematische Schriften Kassel 05, 02 </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt