Inessential features, ineliminable features, and modal logics for model theoretic syntax

Abstract
While monadic second-order logic (MSO) has played a prominent role in model theoretic syntax, modal logics have been used in this context since its inception. When comparing propositional dynamic logic (PDL) to MSO over trees, Kracht (1997) noted that there are tree languages that can be defined in MSO that can only be defined in PDL by adding new features whose distribution is predictable. He named such features “inessential features”. We show that Kracht’s observation can be extended to other modal logics of trees in two ways. First, we demonstrate that for each stronger logic, there exists a tree language that can only be defined in a weaker logic with inessential features. Second, we show that any tree language that can be defined in a stronger logic, but not in some weaker logic, can be defined with inessential features. Additionally, we consider Kracht’s definition of inessential features more closely. It turns out that there are features whose distribution can be predicted, but who fail to be inessential in Kracht’s sense. We will look at ways to modify his definition.
Keywords Model theoretic syntax  Modal logic  Tree automata
Categories (categorize this paper)
DOI 10.1007/s10849-007-9052-3
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 27,621
Through your library
References found in this work BETA

View all 7 references / Add more references

Citations of this work BETA
Querying Linguistic Trees.Catherine Lai & Steven Bird - 2010 - Journal of Logic, Language and Information 19 (1):53-73.

Add more citations

Similar books and articles

Monthly downloads

Added to index

2009-01-28

Total downloads

12 ( #376,432 of 2,168,962 )

Recent downloads (6 months)

1 ( #346,364 of 2,168,962 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums