On h-lexicalized restarting list automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10424377" target="_blank" >RIV/00216208:11320/20:10424377 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.25596/jalc-2020-201" target="_blank" >10.25596/jalc-2020-201</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On h-lexicalized restarting list automata

Popis výsledku v původním jazyce

Following some previous studies on restarting list automata (RLA), we concentrate on a generalized and refined model - the h-lexicalized restarting list automaton (hLxRLA), which is useful for expressing properties of lexicalized syntax in computational linguistics. We present several subclasses of hLxRLA and provide some variants and extensions of the Chomsky hierarchy - the h-lexicalized variants of the Chomsky hierarchy. We compare the input languages of RLA, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages of hLxRLA, which are used to define h-lexicalized syntactic analysis. The h-lexicalized syntactic analysis allows us to stress several nice syntactic properties of h-lexicalized restarting automata (hRLWW). We present a transformation from monotone RLWWautomata that recognize the context-free languages (CFL) as their input languages to deterministic monotone hRLWW-automata that compute h-lexicalized syntactic analysis for the whole class CFL through their basic and h-proper languages. Through this transformation, we obtain several types of deterministic hRLWW-automata and hLxRLA-automata that cover h-lexicalized syntactic analyses of CFL and that satisfy the Complete Strong Correctness Preserving Property.

Název v anglickém jazyce

On h-lexicalized restarting list automata

Popis výsledku anglicky

Following some previous studies on restarting list automata (RLA), we concentrate on a generalized and refined model - the h-lexicalized restarting list automaton (hLxRLA), which is useful for expressing properties of lexicalized syntax in computational linguistics. We present several subclasses of hLxRLA and provide some variants and extensions of the Chomsky hierarchy - the h-lexicalized variants of the Chomsky hierarchy. We compare the input languages of RLA, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages of hLxRLA, which are used to define h-lexicalized syntactic analysis. The h-lexicalized syntactic analysis allows us to stress several nice syntactic properties of h-lexicalized restarting automata (hRLWW). We present a transformation from monotone RLWWautomata that recognize the context-free languages (CFL) as their input languages to deterministic monotone hRLWW-automata that compute h-lexicalized syntactic analysis for the whole class CFL through their basic and h-proper languages. Through this transformation, we obtain several types of deterministic hRLWW-automata and hLxRLA-automata that cover h-lexicalized syntactic analyses of CFL and that satisfy the Complete Strong Correctness Preserving Property.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

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í

2020

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

Journal of Automata, Languages and Combinatorics

ISSN

1430-189X

e-ISSN

—

Svazek periodika

25

Číslo periodika v rámci svazku

2-3

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

34

Strana od-do

201-234

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85089847868