×

On logically defined recognizable tree languages. (English) Zbl 1196.68149

Pandya, Paritosh K. (ed.) et al., FST TCS 2003: Foundations of software technology and theoretical computer science. 23rd conference, Mumbai, India, December 15–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20680-9/pbk). Lect. Notes Comput. Sci. 2914, 195-207 (2003).
Summary: We provide an algebraic characterization of the expressive power of various naturally defined logics on finite trees. These logics are described in terms of Lindström quantifiers, and particular cases include first-order logic and modular logic. The algebraic characterization we give is expressed in terms of a new algebraic structure, finitary preclones, and uses a generalization of the block product operation.
For the entire collection see [Zbl 1029.00064].

MSC:

68Q70 Algebraic theory of languages and automata
03B70 Logic in computer science
08A70 Applications of universal algebra in computer science
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI