Complexity of bifix-free regular languages. (English) Zbl 1429.68110
Summary: We study descriptive complexity properties of the class of regular bifix-free languages, which is the intersection of prefix-free and suffix-free regular languages. We show that there exist universal bifix-free languages that meet all the bounds for the state complexity of basic operations (Boolean operations, product, star, and reversal). This is in contrast with suffix-free languages, where it is known that there does not exist such languages. Then we present a stream of bifix-free languages that is most complex in terms of all basic operations, syntactic complexity, and the number of atoms and their complexities, which requires a superexponential alphabet.
We also complete the previous results by characterizing the state complexity of product, star, and reversal, and establishing tight upper bounds for atom complexities of bifix-free languages. Moreover, we consider the problem of the minimal size of an alphabet required to meet the bounds and the problem of attainable values of state complexities (magic numbers).
We also complete the previous results by characterizing the state complexity of product, star, and reversal, and establishing tight upper bounds for atom complexities of bifix-free languages. Moreover, we consider the problem of the minimal size of an alphabet required to meet the bounds and the problem of attainable values of state complexities (magic numbers).
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
atom complexity; bifix-free; Boolean operations; magic number; most complex; prefix-free; product; quotient complexity; regular language; reversal; state complexity; suffix-free; syntactic complexity; transition semigroupSoftware:
GAPReferences:
| [1] | Berstel, J.; Perrin, D.; Reutenauer, C., Codes and Automata (2009), Cambridge University Press |
| [2] | Jürgensen, H.; Konstantinidis, S., Codes, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 1: Word, Language, Grammar (1997), Springer), 511-607 · Zbl 0866.68057 |
| [3] | Brzozowski, J. A.; Shallit, J.; Xu, Z., Decision problems for convex languages, Inform. and Comput., 209, 353-367 (2011) · Zbl 1217.68125 |
| [4] | Pin, J.-E., Syntactic semigroups, (Handbook of Formal Languages, vol. 1: Word, Language, Grammar (1997), Springer: Springer New York, NY, USA), 679-746 |
| [5] | McNaughton, R.; Papert, S. A., Counter-Free Automata, M.I.T. Research Monograph, vol. 65 (1971), The MIT Press · Zbl 0232.94024 |
| [6] | Brzozowski, J. A.; Tamm, H., Theory of átomata, Theoret. Comput. Sci., 539, 13-27 (2014) · Zbl 1359.68160 |
| [7] | Brzozowski, J. A., In search of the most complex regular languages, Internat. J. Found. Comput. Sci., 24, 6, 691-708 (2013) · Zbl 1410.68199 |
| [8] | GAP - Groups, Algorithms, and Programming (2016) |
| [9] | J.A. Brzozowski, S. Davies, B.Y.V. Liu, Most complex regular ideals, Discrete Math. Theoret. Comput. Sci. 18 (3).; J.A. Brzozowski, S. Davies, B.Y.V. Liu, Most complex regular ideals, Discrete Math. Theoret. Comput. Sci. 18 (3). |
| [10] | Brzozowski, J. A.; Sinnamon, C., Complexity of prefix-convex regular languages, (CIAA. CIAA, Lecture Notes in Comput. Sci., vol. 10329 (2017), Springer), 52-63 · Zbl 1429.68100 |
| [11] | Brzozowski, J. A.; Szykuła, M., Complexity of suffix-free regular languages, (FCT 2015. FCT 2015, Lecture Notes in Comput. Sci., vol. 9210 (2015), Springer), 146-159 · Zbl 1434.68239 |
| [12] | Sinnamon, C., Complexity of proper suffix-convex regular languages, (Câmpeanu, C., CIAA (2018), Springer), 324-338 · Zbl 1509.68140 |
| [13] | Brzozowski, J. A.; Jirásková, G.; Li, B.; Smith, J., Quotient complexity of bifix-, factor-, and subword-free regular languages, Acta Cybernet., 21, 4, 507-527 (2014) · Zbl 1324.68055 |
| [14] | 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) · Zbl 1280.68108 |
| [15] | Szykuła, M.; Wittnebel, J., Syntactic complexity of bifix-free languages, (CIAA. CIAA, Lecture Notes in Comput. Sci., vol. 10329 (2017), Springer), 76-88 · Zbl 1429.68135 |
| [16] | Brzozowski, J. A., Quotient complexity of regular languages, J. Autom. Lang. Comb., 15, 1-2, 71-89 (2010) · Zbl 1345.68200 |
| [17] | Iván, S., Complexity of atoms, combinatorially, Inform. Process. Lett., 116, 5, 356-360 (2016) · Zbl 1352.68130 |
| [18] | Cmorik, R.; Jirásková, G., Basic operations on binary suffix-free languages, (Kotásek, Z.; etal., MEMICS (2012)), 94-102 |
| [19] | Eom, H.-S.; Han, Y.-S.; Jirásková, G., State complexity of basic operations on non-returning regular languages, Fund. Inform., 144, 2, 161-182 (2016) · Zbl 1357.68105 |
| [20] | Jirásková, G.; Palmovský, M.; Šebej, J., Kleene closure on regular and prefix-free languages, (CIAA (2014), Springer), 226-237 · Zbl 1302.68166 |
| [21] | Jirásková, G., On the state complexity of complements, stars, and reversals of regular languages, (DLT (2008), Springer), 431-442 · Zbl 1161.68539 |
| [22] | Šebej, J., Reversal on regular languages and descriptional complexity, (DCFS (2013), Springer), 265-276 · Zbl 1388.68179 |
| [23] | Piccard, S., Sur les bases du group symétrique et du groupe alternant, Comment. Math. Helv., 11, 1, 1-8 (1938) · JFM 64.0063.03 |
| [24] | Brzozowski, J. A.; Davies, S., Most complex non-returning regular languages, (DCFS. DCFS, Lecture Notes in Comput. Sci., vol. 10316 (2017), Springer), 89-101 · Zbl 1426.68139 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
