Tight Bounds for Cut-Operations on Deterministic Finite Automata

• Autorzy: Drewes F. , van der Merwe B. , Holzer M. , Jakobi S.

Identyfikatory

DOI

10.3233/FI-2017-1577

• Języki publikacji: EN

Abstrakty

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 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-andm-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 j-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.

Słowa kluczowe

EN

cut; iterated cut operation; descriptional complexity; finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 89--110
• Opis fizyczny: Bibliogr. 7 poz., rys., tab.

Twórcy

autor

Drewes F.

• Department of Computing Science, Umeå University, Umeå, Sweden

autor

van der Merwe B.

• Department of Mathematical Sciences, Computer Science Division, University of Stellenbosch, Stellenbosch, South Africa

autor

Holzer M.

• Institut für Informatik, Universität Giessen, Giessen, Germany

autor

Jakobi S.

• Institut für Informatik, Universität Giessen, Giessen, Germany

Bibliografia

• [1] Berglund M, Drewes F, van der Merwe B. Analyzing Catastrophic Backtracking Behavior in Practical Regular Expressions Matching. In: ´ Esik Z, Fülöp Z, editors. Proceedings of the 14th International Conference on Automata and Formal Languages. No. 151 in EPTCS. Szeged, Hungary; 2014. p. 109–123. doi:10.4204/EPTCS.151.7.
• [2] Kirrage J, Rathnayake A, Thielecke H. Static Analysis for Regular Expression Denial-of-Service Attacks. In: Lopez J, Huang X, Sandhu R, editors. Proceedings of the 7th International Conference Network and System Security. No. 7873 in LNCS. Madrid, Spain: Springer; 2013. p. 135–148. doi: 10.1007/978-3-642-38631-2_11.
• [3] Clocksin WF, Mellish CS. Programming in Prolog. Springer; 1981. ISBN:978-3-540-11046-0, 978-3-642-96661-3.
• [4] Berglund M, Björklund H, Drewes F, van der Merwe B, Watson B. Cuts in Regular Expressions. In: Béal MP, Carton O, editors. Proceedings of the 17th International Conference Developments in Language Theory. No. 7907 in LNCS. Marne-laVallée, France: Springer; 2011. p. 70–81. doi:10.1007/978-3-642-38771-5_8.
• [5] Harrison MA. Introduction to Formal Language Theory. Addison-Wesley; 1978.
• [6] Graham RL, Knuth DE, Patashnik O. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley; 1994. ISBN-13:978-0201558029, 10:0201558025.
• [7] Piccard S. Sur les bases du groupe symétrique et les couples de substitutions qui engendrent un groupe régulier. Paris: Librairie Vuibert; 1946.