{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:05Z","timestamp":1753894385334,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study the matching problem of regular tree languages, that is, \"$\\exists\n\\sigma:\\sigma(L)\\subseteq R$?\" where $L,R$ are regular tree languages over the\nunion of finite ranked alphabets $\\Sigma$ and $\\mathcal{X}$ where $\\mathcal{X}$\nis an alphabet of variables and $\\sigma$ is a substitution such that\n$\\sigma(x)$ is a set of trees in $T(\\Sigma\\cup H)\\setminus H$ for all $x\\in\n\\mathcal{X}$. Here, $H$ denotes a set of \"holes\" which are used to define a\n\"sorted\" concatenation of trees. Conway studied this problem in the special\ncase for languages of finite words in his classical textbook \"Regular algebra\nand finite machines\" published in 1971. He showed that if $L$ and $R$ are\nregular, then the problem \"$\\exists \\sigma \\forall x\\in \\mathcal{X}:\n\\sigma(x)\\neq \\emptyset\\wedge \\sigma(L)\\subseteq R$?\" is decidable. Moreover,\nthere are only finitely many maximal solutions, the maximal solutions are\nregular substitutions, and they are effectively computable. We extend Conway's\nresults when $L,R$ are regular languages of finite and infinite trees, and\nlanguage substitution is applied inside-out, in the sense of Engelfriet and\nSchmidt (1977\/78). More precisely, we show that if $L\\subseteq\nT(\\Sigma\\cup\\mathcal{X})$ and $R\\subseteq T(\\Sigma)$ are regular tree languages\nover finite or infinite trees, then the problem \"$\\exists \\sigma \\forall x\\in\n\\mathcal{X}: \\sigma(x)\\neq \\emptyset\\wedge \\sigma_{\\mathrm{io}}(L)\\subseteq\nR$?\" is decidable. Here, the subscript \"$\\mathrm{io}$\" in\n$\\sigma_{\\mathrm{io}}(L)$ refers to \"inside-out\". Moreover, there are only\nfinitely many maximal solutions $\\sigma$, the maximal solutions are regular\nsubstitutions and effectively computable. The corresponding question for the\noutside-in extension $\\sigma_{\\mathrm{oi}}$ remains open, even in the\nrestricted setting of finite trees.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:25)2022","type":"journal-article","created":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T12:55:54Z","timestamp":1643806554000},"source":"Crossref","is-referenced-by-count":1,"title":["Regular matching problems for infinite trees"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"given":"Carlos","family":"Camino","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volker","family":"Diekert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Besik","family":"Dundua","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mircea","family":"Marin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e9raud","family":"S\u00e9nizergues","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,2,1]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9023\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9023\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:19:37Z","timestamp":1687292377000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,1]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:25)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2004.09926v5","asserted-by":"subject"},{"id-type":"arxiv","id":"2004.09926v4","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2004.09926","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2004.09926","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,2,1]]},"article-number":"7241"}}