Inessential features, ineliminable features, and modal logics for model theoretic syntax
type: Item
instance of: scholarly article
title: Inessential features, ineliminable features, and modal logics for model theoretic syntax
zbMATH Open document ID: 1192.03004
author: Hans-Jörg Tiede
published in: Journal of Logic, Language and Information
publication date: 2009-03-24T00:00:00Z
review text: This paper further develops the theory of model-theoretic syntax. The author looks at various modal logics for trees with the aim to reach a better understanding of what is a good logic for the formalisation of grammatical theories. The focus of the paper lies on the notion of an \textit{inessential feature}, that has been introduced by \textit{M. Kracht} [Lect. Notes Comput. Sci. 1328, 43--62 (1997; Zbl 0896.03023)]. The main result is a generalization of a theorem by Kracht [loc. cit.]: Any tree language that can be defined in a stronger logic, but not in some weaker logic, can be defined in the weaker logic with inessential features (assumption: all logics involved are weaker than MSO). The theorem is a consequence of a theorem by \textit{J. W. Thatcher} [J. Comput. Syst. Sci. 1, 317--322 (1967; Zbl 0155.01802)]. This shows that the various modal logics for trees differ precisely with respect to which inessential features of trees are eliminable or not. Furthermore, the author argues that the logic MSO might be too strong as a logic for formalizing grammatical theories, because it allows for the elimination of all inessential features.
reviewed by: Clemens Kupke
Mathematics Subject Classification ID: 03B65
Mathematics Subject Classification ID: 03B45
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 91F20
zbMATH DE Number: 5532539
zbMATH Keywords: model-theoretic syntax
zbMATH Keywords: modal logic
zbMATH Keywords: tree automata
MaRDI profile type: Publication
full work available at URL: s10849-007-9052-3
OpenAlex ID: W2021857564
cites work: PDL for ordered trees
cites work: Linguistics, Logic and Finite Trees
cites work: Q4385531
cites work: Q4370234
cites work: Tools and techniques in modal logic
cites work: Q4329243
cites work: Q3409073
cites work: Elementary induction on abstract structures
cites work: Modulo-counting quantifiers over finite trees
cites work: Q4954002
cites work: Q2757841
cites work: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
DOI: 10.1007/S10849-007-9052-3
description: scientific article; zbMATH DE number 5532539