{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:17Z","timestamp":1740133937028,"version":"3.37.3"},"reference-count":21,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["PTDC\/BIA-BIC\/5558\/2014"],"award-info":[{"award-number":["PTDC\/BIA-BIC\/5558\/2014"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["SFRH\/BD\/98202\/2013"],"award-info":[{"award-number":["SFRH\/BD\/98202\/2013"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:p> Forest algebras are defined for investigating languages of forests [ordered sequences] of unranked trees, where a node may have more than two [ordered] successors. They consist of two monoids, the horizontal and the vertical, with an action of the vertical monoid on the horizontal monoid, and a complementary axiom of faithfulness. A pseudovariety is a class of finite algebras of a given signature, closed under the taking of homomorphic images, subalgebras and finitary direct products. By looking at the syntactic congruence for monoids and as the natural extension in the case of forest algebras, we could define a version of syntactic congruence of a subset of the free forest algebra, not just a forest language. Let [Formula: see text] be a finite alphabet and [Formula: see text] be a pseudovariety of finite forest algebras. A language [Formula: see text] is [Formula: see text]-recognizable if its syntactic forest algebra belongs to [Formula: see text]. Separation is a classical problem in mathematics and computer science. It asks whether, given two sets belonging to some class, it is possible to separate them by another set of a smaller class. <\/jats:p><jats:p> Suppose that a forest language [Formula: see text] and a forest [Formula: see text] are given. We want to find if there exists any proof for that [Formula: see text] does not belong to [Formula: see text] just by using [Formula: see text]-recognizable languages, i.e. given such [Formula: see text] and [Formula: see text], if there exists a [Formula: see text]-recognizable language [Formula: see text] which contains [Formula: see text] and does not contain [Formula: see text]. In this paper, we present how one can use profinite forest algebra to separate a forest language and a forest term and also to separate two forest languages. <\/jats:p>","DOI":"10.1142\/s0129054120500276","type":"journal-article","created":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T14:56:32Z","timestamp":1598453792000},"page":"583-593","source":"Crossref","is-referenced-by-count":0,"title":["Weak Separation Problem for Tree Languages"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4440-7211","authenticated-orcid":false,"given":"Saeid","family":"Alirezazadeh","sequence":"first","affiliation":[{"name":"CIBIO, InBIO, CEABN, University Lisbon, Tapada da Ajuda, Lisbon, 1349-017, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2319-8211","authenticated-orcid":false,"given":"Khadijeh","family":"Alibabaei","sequence":"additional","affiliation":[{"name":"Centro de Matematica e Departamento de Matematica, Faculdade de Ciencias, Universidade do Porto, Porto, Portugal"}]}],"member":"219","published-online":{"date-parts":[[2020,8,26]]},"reference":[{"key":"S0129054120500276BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054116500374"},{"key":"S0129054120500276BIB002","first-page":"xviii+511","volume-title":"Series in Algebra","volume":"3","author":"Almeida J.","year":"1994"},{"key":"S0129054120500276BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_27"},{"key":"S0129054120500276BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.018"},{"key":"S0129054120500276BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.46"},{"key":"S0129054120500276BIB007","unstructured":"M. Bojanczyk and  I. Walukiewicz ,  Forest Algebras, Logic and Automata,  Texts Log. Games, Vol.  2  (Amsterdam Univ. Press,  Amsterdam,  2008),  pp. 107\u2013131."},{"key":"S0129054120500276BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_16"},{"key":"S0129054120500276BIB009","unstructured":"K. Denecke and  S. L. Wismath ,  Universal Algebra and Applications in Theoretical Computer Science  (Chapman & Hall\/CRC,  Boca Raton, FL,  2002),  xii+383."},{"key":"S0129054120500276BIB010","unstructured":"S. Eilenberg ,  Automata, Languages, and Machines, Vol.  B  (Academic Press [Harcourt Brace Jovanovich Publishers],  New York,  1976),  xiii+387."},{"key":"S0129054120500276BIB011","unstructured":"S. Eilenberg ,  Automata, Languages, and Machines, Vol.  A  (Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers],  New York,  1974),  xvi+451."},{"key":"S0129054120500276BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.038"},{"key":"S0129054120500276BIB013","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196710005595"},{"key":"S0129054120500276BIB014","unstructured":"F. G\u00e9cseg and  M. Steinby ,  Tree Automata,  Akad\u00e9miai Kiad\u00f3  (Publishing House of the Hungarian Academy of Sciences)  (Budapest,  1984), p.  235."},{"key":"S0129054120500276BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_1"},{"key":"S0129054120500276BIB016","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196795000288"},{"key":"S0129054120500276BIB017","first-page":"125","volume":"188","author":"Gitik R.","year":"1997","journal-title":"JA"},{"key":"S0129054120500276BIB018","unstructured":"T. Place,  L. van Rooijen and  M. Zeitoun ,  Separating Regular Languages by Piecewise Testable and Unambiguous Languages,  Mathematical Foundations of Computer Science, Vol.  2013  (Springer,  Berlin, Heidelberg,  2013),  pp. 729\u2013740."},{"key":"S0129054120500276BIB019","first-page":"751","volume":"179","author":"Ribes L.","year":"1996","journal-title":"JA"},{"issue":"1","key":"S0129054120500276BIB020","first-page":"21","volume":"17","author":"Salehi S.","year":"2005","journal-title":"Acta Cybernetica"},{"key":"S0129054120500276BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.006"},{"volume-title":"General Topology","year":"2004","author":"Willard S.","key":"S0129054120500276BIB023"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500276","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T10:53:40Z","timestamp":1599821620000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8]]},"references-count":21,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["10.1142\/S0129054120500276"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500276","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2020,8]]}}}