On (In)Sensitivity by Two-Way Restarting Automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10389093" target="_blank" >RIV/00216208:11320/18:10389093 - isvavai.cz</a>

Result on the web

<a href="http://ceur-ws.org/Vol-2203/10.pdf" target="_blank" >http://ceur-ws.org/Vol-2203/10.pdf</a>

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On (In)Sensitivity by Two-Way Restarting Automata

Original language description

We study h-lexicalized two-way restarting automaton (hRLWW(i)) that can rewrite at most i times per cycle, for i GREATER-THAN OR EQUAL TO 1. This model is useful for the study of lexical syntactic disambiguation (a notion from linguistic) through the formal notion of h-lexicalized syntactic analysis (hLSA). The hLSA is composed of a basic language and the corresponding h-proper language obtained from the basic language by mapping all non-input symbols on input symbols. We compare the properties of input languages, which are the languages traditionally considered in automata theory, to the properties of hLSA, i.e., to the properties of basic and h-proper languages. The basic and h-proper languages of hRLWW(i)- automata fulfill the so called reduction correctness preserving property, but the input languages do not. While basic and h-proper languages are sensitive to the size of the read/write window, the input languages are not. Moreover, the basic and h-proper languages are sensitive to the number of rewrite steps per cycle. All that concerns a subclass of context-sensitive languages containing all contextfree languages (and most probably also the class of mildly context-sensitive languages [5]), i.e., a class suitable for studying and classifying syntactic and semantic features of natural languages. We work here also with the parametrized constraint of monotonicity. While using the monotonicity of degree one we can characterize the class of context-free languages, the monotonicity of higher degrees can model more complex syntactic phenomena of whole natural languages (like cross-serial dependencies [5]). Finally, we stress the constraint of weak cyclic form. It preserves the power of hRLWW(i)-automata, and it allows to extend the complexity results obtained for the classes of infinite languages also into the classes of finite languages (parametrized by the number of performed cycles). It is useful for classifications in computational and corpus linguistics, where all the (syntactic) observation are of the finite nature. The main technical novelty of the paper are the results about the sensitivity and insensivity of finite and infinite hLSA and corresponding languages by hRLWW(i)- automata.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2018

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

CEUR Workshop Proceedings Vol. 2203

ISBN

978-1-72726-719-8

ISSN

1613-0073

e-ISSN

neuvedeno

Number of pages

8

Pages from-to

10-17

Publisher name

Univerzita P. J. Šafárika

Place of publication

Košice

Event location

Krompachy

Event date

Sep 21, 2018

Type of event by nationality

EUR - Evropská akce

UT code for WoS article

—