Preprint
On the Gap-Complexity of Simple RL-Automata
Abstract
Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages.
This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages.
Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton
that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition.
On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle.
Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.
This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages.
Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton
that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition.
On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle.
Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.
Citation
@article{urn:nbn:de:hebis:34-2006053112600,
author={Mráz, František and Otto, Friedrich and Plátek, Martin},
title={On the Gap-Complexity of Simple RL-Automata},
year={2006}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2006$n2006 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2006053112600 3000 Mráz, František 3010 Otto, Friedrich 3010 Plátek, Martin 4000 On the Gap-Complexity of Simple RL-Automata / Mráz, František 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2006053112600=x R 4204 \$dPreprint 4170 Mathematische Schriften Kassel ;; 06, 02 7136 ##0##urn:nbn:de:hebis:34-2006053112600
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2006-05-31T11:53:52Z 2006-05-31T11:53:52Z 2006 urn:nbn:de:hebis:34-2006053112600 http://hdl.handle.net/123456789/2006053112600 212895 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ analysis by reduction restarting automata gap-complexity complexity of membership problems 004 On the Gap-Complexity of Simple RL-Automata Preprint Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages. open access Mráz, František Otto, Friedrich Plátek, Martin Mathematische Schriften Kassel ;; 06, 02 Mathematische Schriften Kassel 06, 02 </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt