论文标题
有限振荡语言的理性索引
Rational index of bounded-oscillation languages
论文作者
论文摘要
无上下文语言$ l $的有理索引是函数$ f（n）$，因此，对于具有$ n $ state的自动机识别的每个常规语言$ r $，$ l $ and $ l $ and $ r $的交叉点是空的，要么包含一个短的单词短（n）$。众所周知，没有上下文的无上下文可及性问题和与多项式合理索引的无上下文语言（查询）的数据查询评估在NC中，而这些问题在一般情况下是P-Complete。我们研究了有界振荡语言的理性索引，并表明它是多项式秩序的。我们获得了一般有限振荡语言的有理索引值以及其先前研究的子类的上限。
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.
