nach oben

Theory of Computing Systems

Erschienen in:

01.02.2014

Quotient Complexity of Closed Languages

verfasst von: Janusz Brzozowski, Galina Jirásková, Chenglong Zou

Erschienen in: Theory of Computing Systems | Ausgabe 2/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in an analogous way, where by factor we mean contiguous subsequence, and by subword we mean scattered subsequence. We study the state complexity (which we prefer to call quotient complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated applications of positive closure and complement to a closed language result in at most four distinct languages, while Kleene closure and complement give at most eight.

Vorheriger Artikel Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms

Nächster Artikel Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata

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 "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

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

In contrast to some authors, we use a set of initial states, since we require the reverse of an nfa to be an nfa.

Ang, T., Brzozowski, J.: Languages convex with respect to binary relations, and their closure properties. Acta Cybern. 19(2), 445–464 (2009) MATHMathSciNet

Avgustinovich, S.V., Frid, A.E.: A unique decomposition theorem for factorial languages. Int. J. Algebra Comput. 15, 149–160 (2005) CrossRefMATHMathSciNet

Bassino, F., Giambruno, L., Nicaud, C.: Complexity of operations on cofinite languages. In: López-Ortiz, A. (ed.) Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN). LNCS, vol. 6034, pp. 222–233. Springer, Berlin (2010)

Brzozowski, J.: Derivatives of regular expressions. J. ACM 11(4), 481–494 (1964) CrossRefMATHMathSciNet

Brzozowski, J.: Complexity in convex languages. In: Dediu, A.H., Fernau, H., Martin-Vide, C. (eds.) Proceedings of the 4th International Conference on Language and Automata Theory (LATA). LNCS, vol. 6031, pp. 1–15. Springer, Berlin (2010) CrossRef

Brzozowski, J.: Quotient complexity of regular languages. J. Autom. Lang. Comb. 15(1/2), 71–89 (2010)

Brzozowski, J., Grant, E., Shallit, J.: Closures in formal languages and Kuratowski’s theorem. Int. J. Found. Comput. Sci. 22, 301–321 (2011) CrossRefMATHMathSciNet

Brzozowski, J., Jirásková, G., Li, B.: Quotient complexity of ideal languages. Theor. Comput. Sci. 470, 36–52 (2013) CrossRefMATH

Brzozowski, J., Jirásková, G., Li, B., Smith, J.: Quotient complexity of bifix-, factor-, and subword-free languages. In: Dömösi, P., Szabolcs, I. (eds.) Proceedings of the 13th Int. Conference on Automata and Formal Languages (AFL), pp. 123–137. Institute of Mathematics and Informatics, College of Nyíregyháza, Nyíregyháza (2011)

10.

Brzozowski, J., Santean, N.: Predictable semiautomata. Theor. Comput. Sci. 410, 3236–3249 (2009) CrossRefMATHMathSciNet

11.

Brzozowski, J., Shallit, J., Xu, Z.: Decision problems for convex languages. Inf. Comput. 209, 353–367 (2011) CrossRefMATHMathSciNet

12.

Câmpeanu, C., Culik, K. II, Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., Jürgensen, H. (eds.) Revised papers from the 4th International Workshop on Automata Implementation, (WIA). LNCS, vol. 2214, pp. 60–70. Springer, Berlin (2001)

13.

de Luca, A., Varricchio, S.: Some combinatorial properties of factorial languages. In: Capocelli, R. (ed.) Sequences: Combinatorics, Compression, Security, and Transmission, pp. 258–266. Springer, Berlin (1990) CrossRef

14.

Galil, Z., Simon, J.: A note on multiple-entry finite automata. J. Comput. Syst. Sci. 12, 350–351 (1976) CrossRefMATHMathSciNet

15.

Gill, A., Kou, L.T.: Multiple-entry finite automata. J. Comput. Syst. Sci. 9(1), 1–19 (1974) CrossRefMATHMathSciNet

16.

Gruber, H., Holzer, M., Kutrib, M.: The size of Higman-Haines sets. Theor. Comput. Sci. 387, 167–176 (2007) CrossRefMATHMathSciNet

17.

Gruber, H., Holzer, M., Kutrib, M.: More on the size of Higman-Haines sets: effective constructions. Fundam. Inform. 91(1), 105–121 (2009) MATHMathSciNet

18.

Haines, L.H.: On free monoids partially ordered by embedding. J. Comb. Theory 6(1), 94–98 (1969) CrossRefMATHMathSciNet

19.

Han, Y.S., Salomaa, K.: State complexity of basic operations on suffix-free regular languages. Theor. Comput. Sci. 410(27–29), 2537–2548 (2009) CrossRefMATHMathSciNet

20.

Han, Y.S., Salomaa, K., Wood, D.: Operational state complexity of prefix-free regular languages. In: Ésik, Z., Fülöp, Z. (eds.) Automata, Formal Languages, and Related Topics, pp. 99–115. University of Szeged, Szeged (2009)

21.

Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. J. Autom. Lang. Comb. 6, 453–466 (2001) MATHMathSciNet

22.

Jirásek, J., Jirásková, G., Szabari, A.: State complexity of concatenation and complementation. Int. J. Found. Comput. Sci. 16, 511–529 (2005) CrossRefMATH

23.

Kao, J.Y., Rampersad, N., Shallit, J.: On NFAs where all states are final, initial, or both. Theor. Comput. Sci. 410(47–49), 5010–5021 (2009) CrossRefMATHMathSciNet

24.

Kuratowski, C.: Sur l’opération \(\overline{A}\) de l’analysis situs. Fundam. Math. 3, 182–199 (1922) (in French) MATH

25.

Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk SSSR 194, 1266–1268 (1970) (in Russian). English translation: Soviet Math. Dokl. 11, 1373–1375 (1970) MathSciNet

26.

Mirkin, B.G.: On dual automata. Kibernetika 2, 7–10 (1966) (in Russian). English translation: Cybernetics 2, 6–9 (1970) MathSciNet

27.

Okhotin, A.: On the state complexity of scattered substrings and superstrings. Fundam. Inform. 99(3), 325–338 (2010) MATHMathSciNet

28.

Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal’s function. Int. J. Found. Comput. Sci. 13, 145–159 (2002) CrossRefMATHMathSciNet

29.

Thierrin, G.: Convex languages. In: Nivat, M. (ed.) Automata, Languages and Programming, pp. 481–492. North-Holland, Amsterdam (1973)

30.

Veloso, P.A.S., Gill, A.: Some remarks on multiple-entry finite automata. J. Comput. Syst. Sci. 18, 304–306 (1979) CrossRefMATHMathSciNet

31.

Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb. 6, 221–234 (2001) MATHMathSciNet

32.

Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315–328 (1994) CrossRefMATHMathSciNet

Titel: Quotient Complexity of Closed Languages
verfasst von: Janusz Brzozowski
Galina Jirásková
Chenglong Zou
Publikationsdatum: 01.02.2014
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2014
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-013-9515-7

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2014

Growth of Power-Free Languages over Large Alphabets

Balancing Bounded Treewidth Circuits

Encoding Invariance in Average Case Complexity

Approximating the Minimum Length of Synchronizing Words Is Hard

Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms

Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata