Journal article
Authors list: Drewes, Frank; Holzer, Markus; Jakobi, Sebastian; van der Merwe, Brink
Publication year: 2017
Pages: 89-110
Journal: Fundamenta Informaticae
Volume number: 155
Issue number: 1-2
ISSN: 0169-2968
eISSN: 1875-8681
DOI Link: https://doi.org/10.3233/FI-2017-1577
Publisher: SAGE Publications
Abstract:
We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n = 1) . m + n states, otherwise, on DFAs accepting the cut of two individual languages that are accepted by n- and m-state DFAs, respectively. In the unary case we obtain m a x (2n - 1; m + n - 2) states as a tight bound-notice that for m <= n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n -state DFA we find a matching bound of 1 + (n + 1) . F (1; n + 2; n + 2; n + 1 | -1) states on DFAs, if n >= 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude circle minus ((n - 1) !). Finally, the bound drops to 2n - 1 for unary DFAs accepting the iterated cut of an n -state DFA, if n >= 3, and thus is similar to the bound for the cut operation on unary DFAs.
Citation Styles
Harvard Citation style: Drewes, F., Holzer, M., Jakobi, S. and van der Merwe, B. (2017) Tight Bounds for Cut-Operations on Deterministic Finite Automata, Fundamenta Informaticae, 155(1-2), pp. 89-110. https://doi.org/10.3233/FI-2017-1577
APA Citation style: Drewes, F., Holzer, M., Jakobi, S., & van der Merwe, B. (2017). Tight Bounds for Cut-Operations on Deterministic Finite Automata. Fundamenta Informaticae. 155(1-2), 89-110. https://doi.org/10.3233/FI-2017-1577
Keywords
cut and iterated cut operation; DESCRIPTIONAL COMPLEXITY; FINITE AUTOMATA
