Standard

Rational index of bounded-oscillation languages. / Shemetova, Ekaterina; Okhotin, Alexander; Grigorev, Semyon.

в: arXiv, 07.12.2020.

Результаты исследований: Научные публикации в периодических изданияхстатья

Harvard

APA

Shemetova, E., Okhotin, A., & Grigorev, S. (2020). Rational index of bounded-oscillation languages. Рукопись находится на подготовке.

Vancouver

Author

BibTeX

@article{02dc2a3aa54a4c7684334bd58dd61834,
title = "Rational index of bounded-oscillation languages",
abstract = " The rational index of a context-free language $L$ is a function $f(n)$, such that for each regular language $R$ recognized by an automaton with $n$ states, the intersection of $L$ and $R$ is either empty or contains a word shorter than $f(n)$. It is known that the context-free language (CFL-)reachability problem and Datalog query evaluation for context-free languages (queries) with the polynomial rational index is in NC, while these problems is P-complete in the general case. We investigate the rational index of bounded-oscillation languages and show that it is of polynomial order. We obtain upper bounds on the values of the rational index for general bounded-oscillation languages and for some of its previously studied subclasses. ",
keywords = "cs.FL",
author = "Ekaterina Shemetova and Alexander Okhotin and Semyon Grigorev",
year = "2020",
month = dec,
day = "7",
language = "English",
journal = "arXiv",
publisher = "Cornell University",

}

RIS

TY - JOUR

T1 - Rational index of bounded-oscillation languages

AU - Shemetova, Ekaterina

AU - Okhotin, Alexander

AU - Grigorev, Semyon

PY - 2020/12/7

Y1 - 2020/12/7

N2 - The rational index of a context-free language $L$ is a function $f(n)$, such that for each regular language $R$ recognized by an automaton with $n$ states, the intersection of $L$ and $R$ is either empty or contains a word shorter than $f(n)$. It is known that the context-free language (CFL-)reachability problem and Datalog query evaluation for context-free languages (queries) with the polynomial rational index is in NC, while these problems is P-complete in the general case. We investigate the rational index of bounded-oscillation languages and show that it is of polynomial order. We obtain upper bounds on the values of the rational index for general bounded-oscillation languages and for some of its previously studied subclasses.

AB - The rational index of a context-free language $L$ is a function $f(n)$, such that for each regular language $R$ recognized by an automaton with $n$ states, the intersection of $L$ and $R$ is either empty or contains a word shorter than $f(n)$. It is known that the context-free language (CFL-)reachability problem and Datalog query evaluation for context-free languages (queries) with the polynomial rational index is in NC, while these problems is P-complete in the general case. We investigate the rational index of bounded-oscillation languages and show that it is of polynomial order. We obtain upper bounds on the values of the rational index for general bounded-oscillation languages and for some of its previously studied subclasses.

KW - cs.FL

M3 - Article

JO - arXiv

JF - arXiv

ER -

ID: 73555979