diff options
| -rw-r--r-- | mgr.tex | 6 |
1 files changed, 6 insertions, 0 deletions
@@ -247,6 +247,12 @@ range minimum queries on the array. \subsection{Word infix regular queries}\label{wordinfix} +We now turn to a problem about regular languages. Note that the regular language +is fixed, i.e. we treat the size of its representation (e.g. the size of an +automaton representing it) as a parameter. Below we take a deterministic +automaton for convenience, but if we instead start with a nondeterministic +automaton we ``don't care'' about the exponential cost of determinizing it. + \queryproblem[% regular language $L$ over alphabet $\Sigma$, given by DFA $A$. ]{Word Infix Regular Queries}{% |