TY - UNPB

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

U2 - 10.48550/arXiv.2012.03567

DO - 10.48550/arXiv.2012.03567

M3 - Preprint

BT - Rational index of bounded-oscillation languages

ER -