Результаты исследований: Научные публикации в периодических изданиях › статья
Rational index of bounded-oscillation languages. / Shemetova, Ekaterina; Okhotin, Alexander; Grigorev, Semyon.
в: arXiv, 07.12.2020.Результаты исследований: Научные публикации в периодических изданиях › статья
}
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