{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:25:59Z","timestamp":1758709559474,"version":"3.37.3"},"reference-count":31,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>We give an algebraic characterization of the tree languages that are defined by logical formulas using certain Lindstr\u00f6m quantifiers. An important instance of our result concerns first-order definable tree languages. Our characterization relies on the usage of preclones, an algebraic structure introduced by the authors in a previous paper, and of the block product operation on preclones. Our results generalize analogous results on finite word languages, but it must be noted that, as they stand, they do not yield an algorithm to decide whether a given regular tree language is first-order definable.<\/jats:p>","DOI":"10.1142\/s0218196710005595","type":"journal-article","created":{"date-parts":[[2010,5,5]],"date-time":"2010-05-05T09:01:05Z","timestamp":1273050065000},"page":"195-239","source":"Crossref","is-referenced-by-count":5,"title":["ALGEBRAIC CHARACTERIZATION OF LOGICALLY DEFINED TREE LANGUAGES"],"prefix":"10.1142","volume":"20","author":[{"given":"ZOLT\u00c1N","family":"\u00c9SIK","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Szeged, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PASCAL","family":"WEIL","sequence":"additional","affiliation":[{"name":"LaBRI, Universit\u00e9 de Bordeaux, CNRS, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190713"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-08-04712-0"},{"volume":"11","journal-title":"Trans. Computational Logic","author":"Benedikt M.","key":"rf3"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.018"},{"key":"rf8","series-title":"Texts in Logic and Games","volume-title":"Logic and Automata","author":"Boja\u0144czyk M.","year":"2007"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-28788-4"},{"volume-title":"Automata, Languages, and Machines","year":"1976","author":"Eilenberg S.","key":"rf11"},{"key":"rf12","first-page":"711","volume":"54","author":"\u00c9sik Z.","journal-title":"Publicationes Mathematicae"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.034"},{"key":"rf14","doi-asserted-by":"crossref","first-page":"79","DOI":"10.3233\/FUN-2008-821-206","volume":"82","author":"\u00c9sik Z.","journal-title":"Fundamenta Informatic\u00e6"},{"key":"rf15","doi-asserted-by":"crossref","first-page":"61","DOI":"10.3233\/FUN-2008-821-205","volume":"82","author":"\u00c9sik Z.","journal-title":"Fundamenta Informatic\u00e6"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2003017"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.038"},{"key":"rf19","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1051\/ita\/1991250201251","volume":"25","author":"Heuter U.","journal-title":"Theoretical Informatics Applications"},{"key":"rf20","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"Lindstr\u00f6m P.","journal-title":"Theoria"},{"key":"rf21","series-title":"Pure and Applied Mathematics","volume-title":"Infinite Words","volume":"141","author":"Perrin D.","year":"2004"},{"volume-title":"Vari\u00e9t\u00e9s de Langages Formels","year":"1984","author":"Pin J.-E.","key":"rf22"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02127803"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005014"},{"key":"rf25","unstructured":"A.\u00a0Podelski, Tree Automata and Languages, eds. M.\u00a0Nivat and A.\u00a0Podelski (North Holland, 1992)\u00a0pp. 41\u201356."},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90137-0"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90138-2"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90139-4"},{"key":"rf31","first-page":"21","volume":"17","author":"Salehi S.","journal-title":"Acta Cybernetica"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.006"},{"key":"rf33","unstructured":"M.\u00a0Steinby, Tree Automata and Languages, eds. M.\u00a0Nivat and A.\u00a0Podelski (North Holland, 1992)\u00a0pp. 57\u201381."},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00010-3"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90029-I"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00131-X"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196710005595","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T15:09:21Z","timestamp":1740064161000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196710005595"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":31,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1142\/S0218196710005595"],"URL":"https:\/\/doi.org\/10.1142\/s0218196710005595","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}