Tight Bounds for Cut-Operations on Deterministic Finite Automata^*

Issue title: Special Issue on Machines, Computations and Universality (MCU 2015)

Guest editors: Jérôme Durand-Lose, Jarkko Kari and Benedek Nagy

Article type: Research Article

Authors: Drewes, Frank^a | Holzer, Markus^{b; †} | Jakobi, Sebastian^b | van der Merwe, Brink^c

Affiliations: [a] Department of Computing Science, Umeå University, Umeå, Sweden. drewes@cs.umu.se | [b] Institut für Informatik, Universität Giessen, Giessen, Germany. {holzer,sebastian.jakobi}@informatik.uni-giessen.de | [c] Department of Mathematical Sciences, Computer Science Division, University of Stellenbosch, Stellenbosch, South Africa. abvdm@cs.sun.ac.za

Correspondence: [†] Address for correspondence: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Note: [*] This is a completely revised and expanded version of a paper presented at the 7th International Conference Machines, Computation, and Universality (MCU) held in Famagusta, North Cyprus, September 9–11, 2015.

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 max(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 Θ((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.

Keywords: finite automata, cut and iterated cut operation, descriptional complexity

DOI: 10.3233/FI-2017-1577

Journal: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 89-110, 2017