%0 Conference Proceedings
%T State Complexity of Single-Word Pattern Matching in Regular Languages
%+ David R. Cheriton School of Computer Science
%+ Department of Pure Mathematics [Waterloo]
%A Brzozowski, Janusz, A.
%A Davies, Sylvie
%A Madan, Abhishek
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 86-97
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_6
%K All-sided ideal
%K Combined operation
%K Factor
%K Finite automaton
%K Left ideal
%K Pattern matching
%K Prefix
%K Regular language
%K Right ideal
%K State complexity
%K Subsequence
%K Suffix
%K Two-sided ideal
%Z Computer Science [cs]Conference papers
%X The state complexity $$\kappa (L)$$ of a regular language L is the number of states in the minimal deterministic finite automaton recognizing L. In a general pattern-matching problem one has a set T of texts and a set P of patterns; both T and P are sets of words over a finite alphabet $$\varSigma $$. The matching problem is to determine whether any of the patterns appear in any of the texts, as prefixes, or suffixes, or factors, or subsequences. In previous work we examined the state complexity of these problems when both T and P are regular languages, that is, we computed the state complexity of the languages , , , and , where is the shuffle operation. It turns out that the state complexities of these languages match the naïve upper bounds derived by composing the state complexities of the basic operations used in each expression. However, when P is a single word w, and $$\varSigma $$ has two or more letters, the bounds are drastically reduced to the following: ; ; ; and . The bounds for factor and subsequence matching are the same as the naïve bounds, but this is not the case for prefix and suffix matching. For unary languages, we have a tight upper bound of $$m+n-2$$ in all four cases.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387297/document
%2 https://inria.hal.science/hal-02387297/file/480958_1_En_6_Chapter.pdf
%L hal-02387297
%U https://inria.hal.science/hal-02387297
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612