nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection

verfasst von : Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis

Erschienen in: Descriptional Complexity of Formal Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Extended regular expressions (with complement and intersection) are used in many applications due to their succinctness. In particular, regular expressions extended with intersection only (also called semi-extended) can already be exponentially smaller than standard regular expressions or equivalent nondeterministic finite automata (NFA). For practical purposes it is important to study the average behaviour of conversions between these models. In this paper, we focus on the conversion of regular expressions with intersection to nondeterministic finite automata, using partial derivatives and the notion of support. First, we give a tight upper bound of \(2^{O(n)}\) for the worst-case number of states of the resulting partial derivative automaton, where n is the size of the expression. Using the framework of analytic combinatorics, we then establish an upper bound of \((1.056 +o(1))^n\) for its asymptotic average-state complexity, which is significantly smaller than the one for the worst case.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Self-Verifying Finite Automata and Descriptional Complexity

Nächstes Kapitel Unrestricted State Complexity of Binary Operations on Regular Languages

And a more general framework is also reported in [10].

As is the case, for instance, for Brzozowski DFA or Caron et al. approach.

This upper bound corresponds to the case where all unions in \(\pi (\alpha )\) are disjoint.

Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155(2), 291–319 (1996)MathSciNetCrossRefMATH

Antimirov, V.M., Mosses, P.D.: Rewriting extended regular expressions. In: Rozenberg, G., Salomaa, A. (eds.) 1st DLT. pp. 195–209. World Scientific (1994)

Bastos, R.: Manipulation of Extended Regular Expressions with Derivatives. Master’s thesis, Faculdade de Ciências da Universidade do Porto (2015)

Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average state complexity of partial derivative automata. Int. J. Found. Comput. Sci. 22(7), 1593–1606 (2011)MathSciNetCrossRefMATH

Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average size of Glushkov and partial derivative automata. Int. J. Found. Comput. Sci. 23(5), 969–984 (2012)MathSciNetCrossRefMATH

Broda, S., Machiavelo, A., Moreira, N., Reis, R.: A Hitchhiker’s guide to descriptional complexity through analytic combinatorics. Theoret. Comput. Sci. 528, 85–100 (2014)MathSciNetCrossRefMATH

Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Partial derivative automaton for regular expressions with shuffle. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 21–32. Springer, Heidelberg (2015)CrossRef

Brzozowski, J.A.: Derivatives of regular expressions. JACM 11(4), 481–494 (1964)MathSciNetCrossRefMATH

Caron, P., Champarnaud, J.-M., Mignot, L.: Partial derivatives of an extended regular expression. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 179–191. Springer, Heidelberg (2011)CrossRef

10.

Caron, P., Champarnaud, J., Mignot, L.: A general framework for the derivation of regular expressions. RAIRO - Theor. Inf. Appl. 48(3), 281–305 (2014)MathSciNetCrossRefMATH

11.

Champarnaud, J.M., Ziadi, D.: From Mirkin’s prebases to Antimirov’s word partial derivatives. Fundam. Inform. 45(3), 195–205 (2001)MathSciNetMATH

12.

Christiansen, T., Foy, B.D., Wall, L., Orwant, J.: Programming Perl, 4th edn. O’Reilly Media, Sebastopol (2012)MATH

13.

Flajolet, P., Sedgewick, R.: Analytic Combinatorics. CUP, Cambridge (2008)MATH

14.

Fürer, M.: The complexity of the inequivalence problem for regular expressions with intersection. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 234–245. Springer, Heidelberg (1980)CrossRef

15.

Gelade, W.: Succinctness of regular expressions with interleaving, intersection and counting. Theoret. Comput. Sci. 411(31–33), 2987–2998 (2010)MathSciNetCrossRefMATH

16.

Gelade, W., Neven, F.: Succinctness of the complement and intersection of regular expressions. In: Albers, S., Weil, P. (eds.) 25th STACS. LIPIcs, vol. 1, pp. 325–336. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2008)

17.

Gruber, H.: On the descriptional and algorithmic complexity of regular languages. Ph.D. thesis, Justus Liebig University Giessen (2010)

18.

Gruber, H., Holzer, M.: Finite automata, digraph connectivity, and regular expression size. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 39–50. Springer, Heidelberg (2008)CrossRef

19.

Jiang, T., Ravikumar, B.: A note on the space complexity of some decision problems for finite automata. Inf. Process. Lett. 40(1), 25–31 (1991)MathSciNetCrossRefMATH

20.

Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Eng. Cybern. 5, 51–57 (1966)

21.

Petersen, H.: The membership problem for regular expressions with intersection is complete in LOGCFL. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, pp. 513–522. Springer, Heidelberg (2002)CrossRef

22.

Sen, K., Rosu, G.: Generating optimal monitors for extended regular expressions. Electr. Notes Theor. Comput. Sci. 89, 231–250 (2003)

23.

van der Vlist, E.: RELAX NG. O’Reilly Media, Cambridge (2003)

Titel: On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection
verfasst von: Rafaela Bastos
Sabine Broda
António Machiavelo
Nelma Moreira
Rogério Reis
Verlag: Springer International Publishing
Buch: Descriptional Complexity of Formal Systems
Print ISBN: 978-3-319-41113-2

Electronic ISBN: 978-3-319-41114-9

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-41114-9_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"