{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:05:17Z","timestamp":1750219517888,"version":"3.41.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T00:00:00Z","timestamp":1747872000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T00:00:00Z","timestamp":1747872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006690","name":"Politecnico di Milano","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006690","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We extend the notion of the Dyck language from words to two-dimensional arrays of symbols, i.e., pictures, using the row-column combination (also known as the crossword) of two Dyck languages over the same alphabet. In a Dyck crossword picture, each column and each row must be a word from the respective Dyck language. The pairing of open and closed parentheses in a Dyck word can be represented by edges connecting corresponding cells in the same row or column. This defines a <jats:italic>matching graph<\/jats:italic>, which serves as the two-dimensional analogue of the syntactic tree of a Dyck word. A matching graph is partitioned into simple circuits of unbounded length (always a multiple of four), whose labels form a regular language. These circuits exhibit a wide variety of forms and labelings, which we illustrate and partially classify. With a two-letter alphabet, a Dyck crossword is necessarily empty. The minimal non-trivial case, requiring an alphabet of size four, already generates all possible forms of matching graphs and is the primary focus of our study. We prove that the only picture with a single matching circuit (i.e., a Hamiltonian cycle) has size 2 by 2. Two key properties of Dyck words\u2013cancellation and well-nesting\u2013can be generalized to two dimensions, leading to two alternative definitions of 2D Dyck languages: <jats:italic>neutralizable <\/jats:italic> and <jats:italic>well-nested<\/jats:italic>. These languages are special cases of Dyck crossword pictures called quaternate, where all circuits have length 4 (i.e., are rectangles). This results in a strict language inclusion hierarchy: well-nested <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\subset $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2282<\/mml:mo>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> neutralizable <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\subset $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2282<\/mml:mo>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> quaternate <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\subset $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2282<\/mml:mo>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> Dyck crosswords. When the alphabet size exceeds four, not all combinations of row and column Dyck languages yield non-empty crosswords. To identify productive combinations, we introduce an <jats:italic>alphabetic graph<\/jats:italic>, where nodes represent alphabet symbols and edges represent their couplings. A matching circuit corresponds to the unrolling of an alphabetic graph circuit. Finally, we prove that Dyck crosswords are not tiling-recognizable, as expected for a definition extending Dyck word languages to pictures.<\/jats:p>","DOI":"10.1007\/s00236-025-00489-9","type":"journal-article","created":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T19:18:09Z","timestamp":1747941489000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Row-column combination of Dyck words"],"prefix":"10.1007","volume":"62","author":[{"given":"Stefano","family":"Crespi Reghizzi","sequence":"first","affiliation":[]},{"given":"Antonio","family":"Restivo","sequence":"additional","affiliation":[]},{"given":"Pierluigi","family":"San Pietro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,22]]},"reference":[{"key":"489_CR1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/S0049-237X(08)72023-8","volume-title":"Computer Programming and Formal Systems","author":"N Chomsky","year":"1963","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.P.: The algebraic theory of context-free languages. In: Brafford, Hirschenber (ed.) Computer Programming and Formal Systems, pp. 118\u2013161. North-Holland, Amsterdam (1963)"},{"key":"489_CR2","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-031-52113-3_10","volume-title":"SOFSEM 2024: Theory and Practice of Computer Science","author":"S Crespi Reghizzi","year":"2024","unstructured":"Crespi Reghizzi, S., Restivo, A., San Pietro, P.: Row-column combination of Dyck words. In: Fernau, H., Gaspers, S., Klasing, R. (eds.) SOFSEM 2024: Theory and Practice of Computer Science, pp. 139\u2013153. Springer, Berlin (2024)"},{"key":"489_CR3","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-642-59126-6_4","volume-title":"Handbook of Formal Languages","author":"D Giammarresi","year":"1997","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 215\u2013267. Springer, Berlin (1997)"},{"key":"489_CR4","doi-asserted-by":"crossref","unstructured":"Blum, M., Hewitt, C.E.: Automata on a 2-dimensional tape. In: Proceedings of the 8th Annual Symposium on Switching and Automata Theory. IEEE Computer Society Press, Austin, Texas (1967)","DOI":"10.1109\/FOCS.1967.6"},{"key":"489_CR5","doi-asserted-by":"crossref","unstructured":"Matz, O.: Regular expressions and context-free grammars for picture languages. In: 14th Symp. on Theoretical Aspects of Computer Science. LNCS, vol. 1200, pp. 283\u2013294 (1997)","DOI":"10.1007\/BFb0023466"},{"issue":"2 &3","key":"489_CR6","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1142\/S021800149200014X","volume":"6","author":"D Giammarresi","year":"1992","unstructured":"Giammarresi, D., Restivo, A.: Recognizable picture languages. Int. J. Pattern Recognit. Artif. Intell. 6(2 &3), 241\u2013256 (1992). https:\/\/doi.org\/10.1142\/S021800149200014X","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"issue":"2","key":"489_CR7","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0031-3203(98)00072-7","volume":"32","author":"R Siromoney","year":"1999","unstructured":"Siromoney, R., Subramanian, K.G., Dare, V.R., Thomas, D.G.: Some results on picture languages. Patt. Recogn. 32(2), 295\u2013304 (1999)","journal-title":"Patt. Recogn."},{"key":"489_CR8","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1142\/S0218001491000399","volume":"5","author":"M Nivat","year":"1991","unstructured":"Nivat, M., Saoudi, A., Subramanian, K.G., Siromoney, R., Dare, V.R.: Puzzle grammars and context-free array grammars. Int. J. Patt. Recogn. Artif. Intell. 5, 663\u2013676 (1991)","journal-title":"Int. J. Patt. Recogn. Artif. Intell."},{"key":"489_CR9","unstructured":"Pr\u016f\u0161a, D.: Two-dimensional Languages (PhD Thesis). Charles University, Faculty of Mathematics and Physics, Czech Republic (2004)"},{"issue":"1","key":"489_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.tcs.2005.03.041","volume":"340","author":"S Crespi Reghizzi","year":"2005","unstructured":"Crespi Reghizzi, S., Pradella, M.: Tile rewriting grammars and picture languages. Theor. Comput. Sci. 340(1), 257\u2013272 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.03.041","journal-title":"Theor. Comput. Sci."},{"key":"489_CR11","first-page":"474","volume-title":"Grammatical Picture Generation: A Tree-Based Approach","author":"F Drewes","year":"2006","unstructured":"Drewes, F.: Grammatical Picture Generation: A Tree-Based Approach, p. 474. Springer, Berlin (2006)"},{"key":"489_CR12","doi-asserted-by":"publisher","first-page":"303","DOI":"10.4171\/automata-1\/9","volume-title":"Handbook of Automata Theory","author":"S Crespi Reghizzi","year":"2021","unstructured":"Crespi Reghizzi, S., Giammarresi, D., Lonati, V.: Two-dimensional models. In: Pin, J. (ed.) Handbook of Automata Theory, pp. 303\u2013333. European Mathematical Society Publishing House, Berlin (2021)"},{"issue":"2","key":"489_CR13","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/INCO.1997.2659","volume":"138","author":"M Latteux","year":"1997","unstructured":"Latteux, M., Simplot, D.: Context-sensitive string languages and recognizable picture languages. Inf. Comput. 138(2), 160\u2013169 (1997). https:\/\/doi.org\/10.1006\/INCO.1997.2659","journal-title":"Inf. Comput."},{"key":"489_CR14","doi-asserted-by":"publisher","unstructured":"Anselmo, M., Giammarresi, D., Madonia, M.: Classification of string languages via tiling recognizable picture languages. In: Dediu, A., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. Lecture Notes in Computer Science, pp. 105\u2013116. Springer, Berlin (2011). https:\/\/doi.org\/10.1007\/978-3-642-21254-3_7","DOI":"10.1007\/978-3-642-21254-3_7"},{"issue":"1\u20133","key":"489_CR15","doi-asserted-by":"publisher","first-page":"201","DOI":"10.25596\/JALC-2023-201","volume":"28","author":"TJ Smith","year":"2023","unstructured":"Smith, T.J., Salomaa, K.: Recognition and complexity results for projection languages of two-dimensional automata. J. Autom. Lang. Comb. 28(1\u20133), 201\u2013220 (2023). https:\/\/doi.org\/10.25596\/JALC-2023-201","journal-title":"J. Autom. Lang. Comb."},{"issue":"1\u20132","key":"489_CR16","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0304-3975(96)00283-6","volume":"178","author":"M Latteux","year":"1997","unstructured":"Latteux, M., Simplot, D.: Recognizable picture languages and domino tiling. Theor. Comput. Sci. 178(1\u20132), 275\u2013283 (1997). https:\/\/doi.org\/10.1016\/S0304-3975(96)00283-6","journal-title":"Theor. Comput. Sci."},{"key":"489_CR17","doi-asserted-by":"publisher","first-page":"104777","DOI":"10.1016\/j.ic.2021.104777","volume":"286","author":"SA Fenner","year":"2022","unstructured":"Fenner, S.A., Pad\u00e9, D., Thierauf, T.: The complexity of regex crosswords. Inf. Comput. 286, 104777 (2022). https:\/\/doi.org\/10.1016\/j.ic.2021.104777","journal-title":"Inf. Comput."},{"key":"489_CR18","doi-asserted-by":"publisher","first-page":"114598","DOI":"10.1016\/j.tcs.2024.114598","volume":"1002","author":"S Crespi Reghizzi","year":"2024","unstructured":"Crespi Reghizzi, S., Restivo, A., San Pietro, P.: From words to pictures: Row-column combinations and Chomsky-Sch\u00fctzenberger theorem. Theor. Comput. Sci. 1002, 114598 (2024)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"489_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/S0304-3975(98)00328-4","volume":"218","author":"D Simplot","year":"1999","unstructured":"Simplot, D.: A characterization of recognizable picture languages by tilings by finite sets. Theor. Comput. Sci. 218(2), 297\u2013323 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"489_CR20","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/j.patcog.2007.06.018","volume":"41","author":"M Pradella","year":"2008","unstructured":"Pradella, M., Crespi Reghizzi, S.: A SAT-based parser and completer for pictures specified by tiling. Pattern Recognit. 41(2), 555\u2013566 (2008). https:\/\/doi.org\/10.1016\/j.patcog.2007.06.018","journal-title":"Pattern Recognit."},{"issue":"1\u20133","key":"489_CR21","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0012-365X(98)00371-9","volume":"204","author":"E Deutsch","year":"1999","unstructured":"Deutsch, E.: Dyck path enumeration. Discret. Math. 204(1\u20133), 167\u2013202 (1999). https:\/\/doi.org\/10.1016\/S0012-365X(98)00371-9","journal-title":"Discret. Math."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00489-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00489-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00489-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T11:42:38Z","timestamp":1750160558000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00489-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,22]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["489"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00489-9","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2025,5,22]]},"assertion":[{"value":"19 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"23"}}