On the Complexity of Reductions by Restarting Automata.
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10289400" target="_blank" >RIV/00216208:11320/14:10289400 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the Complexity of Reductions by Restarting Automata.
Popis výsledku v původním jazyce
The paper provides linguistic observations as a motivation for a formal study of analysis by reduction (AR). It concentrates on a study of the whole mechanism through a class of restarting automata with meta-instructions using pebbles, delete, and shiftoperations (DS-automata). The complexity of DS-automata is naturally measured by the number of deletions, and the number of word order shifts used in a single meta-instruction. We study reduction languages, backward correctness preserving AR, correctnesspreserving AR, and show unbounded hierarchies (scales) for various classes of reduction languages by the same finite witness languages. The scales make it possible to estimate relevant complexity issues of analysis by reduction for natural languages.
Název v anglickém jazyce
On the Complexity of Reductions by Restarting Automata.
Popis výsledku anglicky
The paper provides linguistic observations as a motivation for a formal study of analysis by reduction (AR). It concentrates on a study of the whole mechanism through a class of restarting automata with meta-instructions using pebbles, delete, and shiftoperations (DS-automata). The complexity of DS-automata is naturally measured by the number of deletions, and the number of word order shifts used in a single meta-instruction. We study reduction languages, backward correctness preserving AR, correctnesspreserving AR, and show unbounded hierarchies (scales) for various classes of reduction languages by the same finite witness languages. The scales make it possible to estimate relevant complexity issues of analysis by reduction for natural languages.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2014
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
NCMA
ISBN
978-3-85403-304-2
ISSN
—
e-ISSN
—
Počet stran výsledku
16
Strana od-do
207-222
Název nakladatele
Österreichische Computer Gesellschaft
Místo vydání
Wien, Austria
Místo konání akce
Kassel, Germany
Datum konání akce
28. 7. 2014
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—