Skip to main content
Article
Inessential Features, Ineliminable Features, and Modal Logics for Model Theoretic Syntax
Journal of Logic, Language and Information (2008)
  • Hans Joerg Tiede, Illinois Wesleyan University
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
Disciplines
Publication Date
2008
Citation Information
Hans Joerg Tiede. "Inessential Features, Ineliminable Features, and Modal Logics for Model Theoretic Syntax" Journal of Logic, Language and Information Vol. 17 Iss. 2 (2008)
Available at: http://works.bepress.com/htiede/7/