nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages

verfasst von : Janusz A. Brzozowski, Corwin Sinnamon

Erschienen in: Language and Automata Theory and Applications

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

A language L over an alphabet \(\varSigma \) is suffix-convex if, for any words \(x,y,z\in \varSigma ^*\), whenever z and xyz are in L, then so is yz. Suffix-convex languages include three special cases: left-ideal, suffix-closed, and suffix-free languages. We examine complexity properties of these three special classes of suffix-convex regular languages. In particular, we study the quotient/state complexity of boolean operations, product (concatenation), star, and reversal on these languages, as well as the size of their syntactic semigroups, and the quotient complexity of their atoms.

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 Two-Dimensional Palindromes and Their Properties

Nächstes Kapitel On the Complexity of Hard Enumeration Problems

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

Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata (Encyclopedia of Mathematics and its Applications). Cambridge University Press, Cambridge (2010)MATH

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

Brzozowski, J.A.: In search of the most complex regular languages. Int. J. Found. Comput. Sci. 24(6), 691–708 (2013)MathSciNetCrossRefMATH

Brzozowski, J.: Unrestricted state complexity of binary operations on regular languages. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 60–72. Springer, Heidelberg (2016). doi:10.1007/978-3-319-41114-9_5 CrossRef

Brzozowski, J.A., Davies, S.: Quotient complexities of atoms in regular ideal languages. Acta Cybern. 22(2), 293–311 (2015)MathSciNetCrossRefMATH

Brzozowski, J.A., Davies, S., Liu, B.Y.V.: Most complex regular ideal languages. Discrete Math. Theoret. Comput. Sci. 18(3) (2016). Paper #5

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

Brzozowski, J.A., Jirásková, G., Zou, C.: Quotient complexity of closed languages. Theory Comput. Syst. 54, 277–292 (2014)MathSciNetCrossRefMATH

10.

Brzozowski, J.A., Li, B., Ye, Y.: Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages. Theoret. Comput. Sci. 449, 37–53 (2012)MathSciNetCrossRefMATH

11.

Brzozowski, J.A., Sinnamon, C.: Complexity of left-ideal, suffix-closed, and suffix-free regular languages (2016). http://arxiv.org/abs/1610.00728

12.

Brzozowski, J.A., Sinnamon, C.: Unrestricted state complexity of binary operations on regular and ideal languages (2016). http://arxiv.org/abs/1609.04439

13.

Brzozowski, J., Szykuła, M.: Upper bounds on syntactic complexity of left and two-sided ideals. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 13–24. Springer, Heidelberg (2014). doi:10.1007/978-3-319-09698-8_2

14.

Brzozowski, J., Szykuła, M.: Complexity of suffix-free regular languages. In: Kosowski, A., Walukiewicz, I. (eds.) FCT 2015. LNCS, vol. 9210, pp. 146–159. Springer, Heidelberg (2015). doi:10.1007/978-3-319-22177-9_12. Full paper at http://arxiv.org/abs/1504.05159

15.

Brzozowski, J.A., Szykuła, M., Ye, Y.: Syntactic complexity of regular ideals, (September 2015). http://arxiv.org/abs/1509.06032

16.

Brzozowski, J.A., Tamm, H.: Quotient complexities of atoms of regular languages. Int. J. Found. Comput. Sci. 24(7), 1009–1027 (2013)CrossRefMATH

17.

Brzozowski, J.A., Tamm, H.: Theory of átomata. Theoret. Comput. Sci. 539, 13–27 (2014)MathSciNetCrossRefMATH

18.

Brzozowski, J., Ye, Y.: Syntactic complexity of ideal and closed languages. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 117–128. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22321-1_11 CrossRef

19.

Cmorik, R., Jirásková, G.: Basic operations on binary suffix-free languages. In: Kotásek, Z., Bouda, J., Černá, I., Sekanina, L., Vojnar, T., Antoš, D. (eds.) MEMICS 2011. LNCS, vol. 7119, pp. 94–102. Springer, Heidelberg (2012). doi:10.1007/978-3-642-25929-6_9 CrossRef

20.

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

21.

Holzer, M., König, B.: On deterministic finite automata and syntactic monoid size. Theoret. Comput. Sci. 327(3), 319–347 (2004)MathSciNetCrossRefMATH

22.

Iván, S.: Complexity of atoms, combinatorially. Inform. Process. Lett. 116(5), 356–360 (2016)MathSciNetCrossRefMATH

23.

Jirásková, G., Olejár, P.: State complexity of union and intersection of binary suffix-free languages. In: Bordihn, H., et al. (eds.) NMCA, pp. 151–166. Austrian Computer Society (2009)

24.

Krawetz, B., Lawrence, J., Shallit, J.: State complexity and the monoid of transformations of a finite set. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 213–224. Springer, Heidelberg (2005). doi:10.1007/978-3-540-30500-2_20 CrossRef

25.

Myhill, J.: Finite automata and representation of events. Wright Air Development Center. Technical report, pp. 57–624 (1957)

26.

Pin, J.E.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. vol. 1: Word, Language, Grammar, pp. 679–746. Springer, New York (1997)CrossRef

27.

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

28.

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

Titel: Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages
verfasst von: Janusz A. Brzozowski
Corwin Sinnamon
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-319-53732-0

Electronic ISBN: 978-3-319-53733-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-53733-7_12

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"