Attributes | Values |
---|
rdf:type
| |
Description
| - 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. Here we introduce and study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 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-sRL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-sRL-automata with an unbounded number of gaps accept NP-complete languages.
- 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. Here we introduce and study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 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-sRL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-sRL-automata with an unbounded number of gaps accept NP-complete languages. (en)
- Redukční analýza je metodou používanou v lingvistice pro kontrolu správnosti vět přirozených jazyků. Tato metoda je modelována pomocí restartovacích automatů. Zde se zavádí a studuje nový typ restartovacích automatů, tak zvaný t-sRL-automat, jenž je RL-automatem s pracovním oknem velikosti 1, a který splňuje podmínku minimální acceptance. Na druhé straně, může provádět až vypouštěcích kroků v cyklu. Zde studujeme tzv. gap-complexity těchto automatů. Membership problém pro jazyky přijímané pomocí t-sRL-automatů s omezeným počtem děr (gaps) je řešitelný v polynomiálním čase. Na druhé straně, t-sRL-automaty neomezeým počtem děr přijímají NP-úplné jazyky. (cs)
|
Title
| - On the Gap-Complexity of Simple RL-Automata
- O děrové-složitosti jednoduchých RL- automatů (cs)
- On the Gap-Complexity of Simple RL-Automata (en)
|
skos:prefLabel
| - On the Gap-Complexity of Simple RL-Automata
- O děrové-složitosti jednoduchých RL- automatů (cs)
- On the Gap-Complexity of Simple RL-Automata (en)
|
skos:notation
| - RIV/00216208:11320/06:00002821!RIV07-GA0-11320___
|
http://linked.open.../vavai/riv/strany
| |
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(1ET100300517), P(GA201/04/2102), Z(MSM0021620838)
|
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216208:11320/06:00002821
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - Gap-Complexity; Simple; RL-Automata (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| - Lecture Notes In Computer Science
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| - Mráz, František
- Plátek, Martin
|
http://linked.open...n/vavai/riv/zamer
| |
issn
| |
number of pages
| |
http://localhost/t...ganizacniJednotka
| |