On (In)Sensitivity by Two-Way Restarting Automata

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

On (In)Sensitivity by Two-Way Restarting Automata

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On (In)Sensitivity by Two-Way Restarting Automata

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

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ů

Název statě ve sborníku

CEUR Workshop Proceedings Vol. 2203

ISBN

978-1-72726-719-8

ISSN

1613-0073

e-ISSN

neuvedeno

Počet stran výsledku

8

Strana od-do

10-17

Název nakladatele

Univerzita P. J. Šafárika

Místo vydání

Košice

Místo konání akce

Krompachy

Datum konání akce

21. 9. 2018

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—