One-Way Restarting Automata and Their Sensitivity

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

Result on the web

<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>

Result language

angličtina

Original language name

One-Way Restarting Automata and Their Sensitivity

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

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

2022

Confidentiality

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

Name of the periodical

International Journal of Foundations of Computer Science

ISSN

0129-0541

e-ISSN

1793-6373

Volume of the periodical

33

Issue of the periodical within the volume

03N04

Country of publishing house

SG - SINGAPORE

Number of pages

17

Pages from-to

371-387

UT code for WoS article

000797246300011

EID of the result in the Scopus database

2-s2.0-85129471268