On the Complexity of Reductions by Restarting Automata.

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On the Complexity of Reductions by Restarting Automata.

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2014

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

NCMA

ISBN

978-3-85403-304-2

ISSN

—

e-ISSN

—

Number of pages

16

Pages from-to

207-222

Publisher name

Österreichische Computer Gesellschaft

Place of publication

Wien, Austria

Event location

Kassel, Germany

Event date

Jul 28, 2014

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—