Change search
ReferencesLink to record
Permanent link

Direct link
Tight Bounds for Cut-Operations on Deterministic Finite Automata
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)ORCID iD: 0000-0001-7349-7693
Universität Giessen.
Universität Giessen.
University of Stellenbosch.
2015 (English)In: Machines, Computations, and Universality: 7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings / [ed] J. Durand-Lose and B. Nagy, Springer Publishing Company, 2015, Vol. 9288, 45-60 p.Conference paper (Refereed)
Abstract [en]

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−1)⋅m+n(n−1)⋅m+n states 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)max(2n−1,m+n−2) states as a tight bound. 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)1+(n+1)⋅F(1,n+2,−n+2;n+1∣−1) states on DFAs, where FF refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n−1)!)Θ((n−1)!). Finally, the bound drops to 2n−12n−1 for unary DFAs accepting the iterated cut of an n-state DFA and thus is similar to the bound for the cut operation on unary DFAs.

Place, publisher, year, edition, pages
Springer Publishing Company, 2015. Vol. 9288, 45-60 p.
, Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Computer Science
Research subject
Computer Science
URN: urn:nbn:se:umu:diva-104114DOI: 10.1007/978-3-319-23111-2_4ISI: 000363670900004ISBN: 978-3-319-23111-2ISBN: 978-3-319-23110-5OAI: diva2:817777
7th Conference on Machines, Computations and Universality (MCU 2015)
Available from: 2015-06-06 Created: 2015-06-06 Last updated: 2016-06-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 95 hits
ReferencesLink to record
Permanent link

Direct link