A Special Issue in Memory of Bret TilsonNo Access

ALGEBRAIC CHARACTERIZATION OF LOGICALLY DEFINED TREE LANGUAGES

ZOLTÁN ÉSIK

Department of Computer Science, University of Szeged, Hungary

Search for more papers by this author

and

PASCAL WEIL

LaBRI, Université de Bordeaux, CNRS, France

Corresponding author. Postal address: LaBRI, 351 cours de la Libération, 33405 Talence Cedex, France.

Search for more papers by this author

https://doi.org/10.1142/S0218196710005595Cited by:4 (Source: Crossref)

Abstract

We give an algebraic characterization of the tree languages that are defined by logical formulas using certain Lindström 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.

This paper was prepared while the first author was affiliated with Rovira i Virgili University, Tarragona, Spain. The first author acknowledges partial support from grant MTM2007 63422 from the Ministry of Education and Science of Spain. The second author acknowledges partial support from the French ANR (projet DOTS) and the Indo-French project TIMED DISCOVERI. Both authors acknowledge support from the European Science Foundation program AUTOMATHA and from CNRS-HAS.

Dedicated to the Memory of Bret Tilson

Keywords:

AMSC: F.4.3, F.4.1, 03B70, 68Q70, 68Q45

References

J. Almeida, Algebra Universalis 27, 333 (1990), DOI: 10.1007/BF01190713. Crossref, Web of Science, Google Scholar
J. Almeidaet al., Trans. Amer. Math. Soc. 361, 1429 (2009), DOI: 10.1090/S0002-9947-08-04712-0. Crossref, Web of Science, Google Scholar
M. Benedikt and L. Ségoufin, Trans. Computational Logic 11, (2009). Google Scholar
M. Bojańczyk, Two-way unary temporal logic over trees, LICS 2007 (IEEE) pp. 121–130. Google Scholar
M. Bojańczyk and L. Ségoufin, Tree languages defined in first-order logic with one quantifier alternation, ICALP 2008, Lecture Notes in Computer Science 5126, eds. L. Acetoet al. (Springer, 2008) pp. 233–245. Google Scholar
M. Bojańczyk, L. Ségoufin and H. Straubing, Piecewise testable tree languages, LICS 2008 (IEEE) pp. 442–451. Google Scholar
M. Bojańczyk and I. Walukiewicz, Theoret. Comput. Sci. 358, 255 (2006), DOI: 10.1016/j.tcs.2006.01.018. Crossref, Web of Science, Google Scholar
M. Bojańczyk and I. Walukiewicz , Logic and Automata , Texts in Logic and Games , eds. J. Flum , E. Graedel and T. Wilke ( Amsterdam University Press , 2007 ) . Google Scholar
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, Tree automata techniques and applications, http://www.grappa.univ-lille3.fr/tata . Google Scholar
H.-D. Ebbinghaus and J. Flum , Finite Model Theory ( Springer , 1995 ) . Crossref, Google Scholar
S. Eilenberg , Automata, Languages, and Machines A and B ( Academic Press , 1976 ) . Google Scholar
Z. Ésik, Publicationes Mathematicae 54, 711 (1999). Google Scholar
Z. Ésik, Theoret. Computer Science 356, 136 (2006), DOI: 10.1016/j.tcs.2006.01.034. Crossref, Web of Science, Google Scholar
Z. Ésik and Sz. Iván, Fundamenta Informaticæ 82, 79 (2008). Web of Science, Google Scholar
Z. Ésik and Sz. Iván, Fundamenta Informaticæ 82, 61 (2008). Web of Science, Google Scholar
Z. Ésik and K. G. Larsen, Theoretical Informatics Applications 37, 179 (2003), DOI: 10.1051/ita:2003017. Crossref, Web of Science, Google Scholar
Z. Ésik and P. Weil, On logically defined recognizable tree languages, Proc. FST TCS 2003, Lecture Notes in Computer Science 2914, eds. P. K. Pandya and J. Radhakrishnan (Springer, 2003) pp. 195–207. Google Scholar
Z. Ésik and P. Weil, Theoretical Computer Science 340, 291 (2005), DOI: 10.1016/j.tcs.2005.03.038. Crossref, Web of Science, Google Scholar
U. Heuter, Theoretical Informatics Applications 25, 125 (1991). Crossref, Web of Science, Google Scholar
P. Lindström, Theoria 32, 186 (1966). Crossref, Google Scholar
D. Perrin and J.-E. Pin , Infinite Words , Pure and Applied Mathematics 141 ( Elsevier , 2004 ) . Google Scholar
J.-E. Pin , Variétés de Langages Formels ( Masson , Paris , 1984 ) . Google Scholar
J.-E. Pin, Annals Mathematics Artificial Intelligence 16, 343 (1996), DOI: 10.1007/BF02127803. Crossref, Web of Science, Google Scholar
J.-E. Pin and H. Straubing, Theoret. Informatics Appl. 39, 239 (2005), DOI: 10.1051/ita:2005014. Crossref, Web of Science, Google Scholar
A. Podelski, Tree Automata and Languages, eds. M. Nivat and A. Podelski (North Holland, 1992) pp. 41–56. Google Scholar
A. Potthoff, First order logic on finite trees, TAPSOFT '95, Lecture Notes in Computer Science 915, eds. P. D. Mosses, M. Nielsen and M. I. Schwartzbach (Springer, 1995) pp. 125–139. Google Scholar
A. Potthoff and W. Thomas, Regular tree languages without unary symbols are star-free, FCT 93, Lecture Notes in Computer Science 710, ed. Z. Ésik (Springer, 1993) pp. 396–405. Google Scholar
J. Rhodes and B. Tilson, J. Pure Appl. Algebra 62, 227 (1989), DOI: 10.1016/0022-4049(89)90137-0. Crossref, Web of Science, Google Scholar
J. Rhodes and P. Weil, J. Pure Appl. Algebra 62, 269 (1989), DOI: 10.1016/0022-4049(89)90138-2. Crossref, Web of Science, Google Scholar
J. Rhodes and P. Weil, J. Pure Appl. Algebra 62, 285 (1989), DOI: 10.1016/0022-4049(89)90139-4. Crossref, Web of Science, Google Scholar
S. Salehi, Acta Cybernetica 17, 21 (2005). Google Scholar
S. Salehi and M. Steinby, Theoret. Comput. Sci. 377, 1 (2007), DOI: 10.1016/j.tcs.2007.02.006. Crossref, Web of Science, Google Scholar
M. Steinby, Tree Automata and Languages, eds. M. Nivat and A. Podelski (North Holland, 1992) pp. 57–81. Google Scholar
M. Steinby, Theoret. Comput. Sci. 205, 1 (1998), DOI: 10.1016/S0304-3975(98)00010-3. Crossref, Web of Science, Google Scholar
H. Straubing , Finite Automata, Formal Logic, and Circuit Complexity ( Birkhaüser , 1994 ) . Crossref, Google Scholar
H. Straubing, On logical descriptions of regular languages, LATIN 2002, Lecture Notes in Computer Science 2286 (Springer, 2002) pp. 528–538. Google Scholar
W. Thomas, Handbook of Formal Languages III, eds. G. Rozenberg and A. Salomaa (Springer, 1997) pp. 389–455. Crossref, Google Scholar
P. Weil, J. Computing System Science 45, 316 (1992), DOI: 10.1016/0022-0000(92)90029-I. Crossref, Web of Science, Google Scholar
P. Weil, Algebraic recognizability of languages, MFCS 2004, Lecture Notes in Computer Science 3153, eds. J. Fiala, V. Koubek and J. Kratochvíl (Springer, 2004) pp. 149–175. Google Scholar
Th. Wilke, Theoret. Comput. Sci. 154, 85 (1996), DOI: 10.1016/0304-3975(95)00131-X. Crossref, Web of Science, Google Scholar