David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 17 (2):217-227 (2008)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Yiannis N. Moschovakis (1974/2008). Elementary Induction on Abstract Structures. Dover Publications.
Loredana Afanasiev, Patrick Blackburn, Ioanna Dimitriou, Bertrand Gaiffe, Evan Goris, Maarten Marx & Maarten de Rijke (2005). PDL for Ordered Trees. Journal of Applied Non-Classical Logics 15 (2):115-135.
Hans Kamp (1968). Tense Logic and the Theory of Linear Order. Dissertation, Ucla
Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (2002). Advances in Modal Logic. Bulletin of Symbolic Logic 8 (1):95-97.
Citations of this work BETA
Catherine Lai & Steven Bird (2010). Querying Linguistic Trees. Journal of Logic, Language and Information 19 (1):53-73.
Similar books and articles
Marcus Kracht & Frank Wolter (1997). Simulation and Transfer Results in Modal Logic – a Survey. Studia Logica 59 (2):149-177.
Franz Baader & Ulrike Sattler (2001). An Overview of Tableau Algorithms for Description Logics. Studia Logica 69 (1):5-40.
Johan Van Benthem, Giovanna D'Agostino, Angelo Montanari & Alberto Policriti (1998). Modal Deduction in Second-Order Logic and Set Theory: II. Studia Logica 60 (3):387 - 420.
Johan van Benthem, Giovanna D'Agostino, Angelo Montanari & Alberto Policriti (1998). Modal Deduction in Second-Order Logic and Set Theory - II. Studia Logica 60 (3):387-420.
George E. Weaver (1994). Syntactic Features and Synonymy Relations: A Unified Treatment of Some Proofs of the Compactness and Interpolation Theorems. Studia Logica 53 (2):325 - 342.
Matthew W. McKeon (2010). The Concept of Logical Consequence: An Introduction to Philosophical Logic. Peter Lang Pub..
Minghui Ma (2010). Toward Model-Theoretic Modal Logics. Frontiers of Philosophy in China 5 (2):294-311.
Added to index2009-01-28
Total downloads8 ( #266,667 of 1,724,748 )
Recent downloads (6 months)2 ( #268,625 of 1,724,748 )
How can I increase my downloads?