One-Way Restarting Automata and Their Sensitivity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10456335" target="_blank" >RIV/00216208:11320/22:10456335 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=7NK1urvjjb" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=7NK1urvjjb</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1142/S0129054122410106" target="_blank" >10.1142/S0129054122410106</a>

Jazyk výsledku

angličtina

Název v původním jazyce

One-Way Restarting Automata and Their Sensitivity

Popis výsledku v původním jazyce

Here we establish and study some rigorous tools suitable for the lexicalized syntactic analysis (LSA) of natural and formal languages. Motivated by the linguistic method of analysis by reduction, we are interested in correctness preserving LSA. We introduce a suitable model of automata, the h-lexicalized one-way restarting automata (h-RRWW), and compare the properties of their input languages, which are the languages considered traditionally in automata theory, to the properties of the so-called basic and h-proper languages. These languages form the basic components for LSA. With respect to their input languages, h-RRWW-automata are not sensitive to the size of the read/write window and they allow computations that are far from being correctness preserving. On the other hand, for their basic and h-proper languages, h-RRWW-automata ensure that the resulting computations are completely correctness preserving, and they yield infinite ascending hierarchies of language classes within the regular, the context-free, and the context-sensitive languages that are based on the size of the read/write window.

Název v anglickém jazyce

One-Way Restarting Automata and Their Sensitivity

Popis výsledku anglicky

Here we establish and study some rigorous tools suitable for the lexicalized syntactic analysis (LSA) of natural and formal languages. Motivated by the linguistic method of analysis by reduction, we are interested in correctness preserving LSA. We introduce a suitable model of automata, the h-lexicalized one-way restarting automata (h-RRWW), and compare the properties of their input languages, which are the languages considered traditionally in automata theory, to the properties of the so-called basic and h-proper languages. These languages form the basic components for LSA. With respect to their input languages, h-RRWW-automata are not sensitive to the size of the read/write window and they allow computations that are far from being correctness preserving. On the other hand, for their basic and h-proper languages, h-RRWW-automata ensure that the resulting computations are completely correctness preserving, and they yield infinite ascending hierarchies of language classes within the regular, the context-free, and the context-sensitive languages that are based on the size of the read/write window.

Druh

J_imp - Článek v periodiku v databázi Web of Science

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í

2022

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 periodika

International Journal of Foundations of Computer Science

ISSN

0129-0541

e-ISSN

1793-6373

Svazek periodika

33

Číslo periodika v rámci svazku

03N04

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

17

Strana od-do

371-387

Kód UT WoS článku

000797246300011

EID výsledku v databázi Scopus

2-s2.0-85129471268