×

Context-freeness of Word-MIX languages. (English) Zbl 07601079

Jonoska, Nataša (ed.) et al., Developments in language theory. 24th international conference, DLT 2020, Tampa, FL, USA, May 11–15, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12086, 304-318 (2020).
Summary: In this paper we provide a decidable characterisation of the context-freeness of a Word-MIX language \(L_{\!A}(w_1, \ldots, w_k)\), where \(L_{\!A}(w_1, \ldots, w_k)\) is the set of all words over \(A\) that contain the same number of subword occurrences of parameter words \(w_1, \ldots, w_k\).
For the entire collection see [Zbl 1496.68024].

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Joshi, A., Vijay-Shanker, K., Weir, D.: The convergence of mildly context-sensitive grammar formalisms. Foundational Issues in Natural Language Processing, pp. 31-82 (1991)
[2] Marsh, W.: Some conjectures on indexed languages. Abstract Appears J. Symb. Log. 51(3), 849 (1985)
[3] Boullier, P.: Chinese numbers, mix, scrambling, and concatenation grammars range. In: EACL 1999, 9th Conference of the European Chapter of the Association for Computational Linguistics, 8-12 June 1999, University of Bergen, Bergen, Norway, pp. 53-60. The Association for Computer Linguistics (1999)
[4] Kanazawa, M., Salvati, S.: MIX is not a tree-adjoining language. In: The 50th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, 8-14 July 2012, Jeju Island, Korea - Volume 1: Long Papers, pp. 666-674. The Association for Computer Linguistics (2012)
[5] Salvati, S.: MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies. J. Comput. Syst. Sci. 81(7), 1252-1277 (2015) · Zbl 1325.68133 · doi:10.1016/j.jcss.2015.03.004
[6] Parikh, R.: On context-free languages. J. ACM 13(4), 570-581 (1966) · Zbl 0154.25801 · doi:10.1145/321356.321364
[7] Colbourn, C.J., Dougherty, R.E., Lidbetter, T.F., Shallit, J.: Counting subwords and regular languages. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 231-242. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98654-8_19 · Zbl 1404.68067 · doi:10.1007/978-3-319-98654-8_19
[8] Mateescu, A., Salomaa, A., Salomaa, K., Yu, S.: A sharpening of the Parikh mapping. Theor. Inf. Appl. 35(6), 551-564 (2001) · Zbl 1005.68092 · doi:10.1051/ita:2001131
[9] Mateescu, A., Salomaa, A., Yu, S.: Subword histories and Parikh matrices. J. Comput. Syst. Sci. 68(1), 1-21 (2004) · Zbl 1072.68085 · doi:10.1016/j.jcss.2003.04.001
[10] Seki, S.: Absoluteness of subword inequality is undecidable. Theoret. Comput. Sci. 418, 116-120 (2012) · Zbl 1232.68086 · doi:10.1016/j.tcs.2011.10.017
[11] Cadilhac, M., Finkel, A., McKenzie, P.: Unambiguous constrained automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 239-250. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31653-1_22 · Zbl 1370.68161 · doi:10.1007/978-3-642-31653-1_22
[12] Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, Inc., New York (1966) · Zbl 0184.28401
[13] Kászonyi, L.: A pumping lemma for DLI-languages. Discrete Math. 258(1), 105-122 (2002) · Zbl 1052.68077 · doi:10.1016/S0012-365X(02)00265-0
[14] Leroux, J., Penelle, V., Sutre, G.: The context-freeness problem is coNP-complete for flat counter systems. In: Cassez, F., Raskin, J.-F. (eds.) ATVA 2014. LNCS, vol. 8837, pp. 248-263. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11936-6_19 · Zbl 1448.68270 · doi:10.1007/978-3-319-11936-6_19
[15] Schwer, S.R.: The context-freeness of the languages associated with vector addition systems is decidable. Theoret. Comput. Sci. 98(2), 199-247 (1992) · Zbl 0769.68067 · doi:10.1016/0304-3975(92)90002-W
[16] Sin’ya, R.: Context-freeness of word-mix languages (full version) (2020). http://www.math.akita-u.ac.jp/ ryoma/misc/dlt2020full.pdf
[17] de Luca, A., Varricchio, S.: Finiteness and Regularity in Semigroups and Formal Languages. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-642-59849-4 · Zbl 0935.68056 · doi:10.1007/978-3-642-59849-4
[18] Sin’ya, R.: Note on the infiniteness of \({L}(w_1, \ldots , w_k)\). CoRR abs/1812.02600 (2018)
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.