Skip to main content
Log in

Inessential Features, Ineliminable Features, and Modal Logics for Model Theoretic Syntax

Journal of Logic, Language and Information Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Afanasiev L., Blackburn P., Dimitriou I., Gaiffe B., Goris E., Marx M., de Rijke M. (2005) PDL for ordered trees. Journal of Applied Non-Classical Logic 15(2): 115–135

    Article  Google Scholar 

  • Blackburn P., Meyer-Viol W. (1994). Linguistics, logic and finite trees. Logic Journal of the IGPL, 2(1): 3–29

    Article  Google Scholar 

  • Cornell T., Rogers J. (2000). Model theoretic syntax. In: Cheng L.L.-S., Sybesma R. (eds) The GLOT international state-of-the-article book. Berlin, de Gruyter, pp. 177–198

    Google Scholar 

  • Courcelle, B. (1990). Graph rewriting: An algebraic and logic approach. In: J. van Leeuwen (Ed.), Handbook of theoretical computer science (Vol. B, Chapt. 5, pp. 193–242). Elsevier.

  • Gécseg, F., & Steinby, M. (1997). Tree languages. In: G. Rozenberg, & A. Salomaa (Eds.), Handbook of formal languages (Vol. 3, pp. 1–68). Springer.

  • Kamp, H. (1968). Tense logic and the theory of linear order. Ph.D. thesis, University of California, Los Angeles.

  • Kracht M. (1997). Inessential features. In: Lecomte A., Lamarche F., Perrier G. (eds) Logical aspects of computational linguistics. Berlin, Springer, pp. 43–62

    Chapter  Google Scholar 

  • Kracht M. (1999). Tools and techniques in modal logic. Amsterdam, North-Holland

    Book  Google Scholar 

  • Kracht M. (2001). Logic and syntax—a personal perspective. In: Zakharyaschev M., Segerberg K., de Rijke M., Wansing H. (eds) Advances in modal logic (Vol. 2). Stanford, CSLI Publications, pp. 337–366

    Google Scholar 

  • Kracht M. (2003). The mathematics of language. Berlin, de Gruyter

    Google Scholar 

  • Moschovakis, Y. (1974). Elementary induction on abstract structures. North-Holland Publishing Company.

  • Moss L.S., Tiede H.-J. (2006). Applications of modal logic in linguistics. In: Blackburn P., van Benthem J., Wolter F. (eds) Handbook of modal logic. Amsterdam, Elsevier, pp. 1031–1076

    Google Scholar 

  • Palm A. (1997). Transforming tree constraints into formal grammars. Berlin, Akademische Verlagsgesellschaft Aka GmbH

    Google Scholar 

  • Potthoff A. (1994). Modulo-counting quantifiers over finite trees. Theoretical Computer Science 126(1): 97–112

    Article  Google Scholar 

  • Rogers J. (1997). Strict LT2: Regular :: local : recognizable. In: Retoré C. (eds) Logical aspects of computational linguistics (Nancy, 1996). Berlin, Springer, pp. 366–385

    Chapter  Google Scholar 

  • Rogers J. (1998). A descriptive approach to language-theoretic complexity. Stanford, CSLI Publications

    Google Scholar 

  • Schlingloff, B.-H. (1992). On the expressive power of modal logics on trees. In: A. Nerode & M. A. Taitslin (Eds.), Logical foundations of computer science—Tver ’92, Second International Symposium, Tver, Russia, July 20–24, 1992, Proceedings (pp. 441–451). Berlin: Springer-Verlag.

  • Thatcher J.W. (1967). Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Journal of Computer and System Sciences 1, 317–322

    Google Scholar 

  • Thatcher J.W., Wright J.B. (1968). Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory 2, 57–81

    Article  Google Scholar 

  • Volger H. (1999). Principle languages and principle based parsing. In: Kolb H.-P., Mönnich U. (eds) The mathematics of syntactic structure. Berlin, de Gruyter, pp. 83–111

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Hans-Jörg Tiede.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tiede, HJ. Inessential Features, Ineliminable Features, and Modal Logics for Model Theoretic Syntax. J of Log Lang and Inf 17, 217–227 (2008). https://doi.org/10.1007/s10849-007-9052-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10849-007-9052-3

Keywords

Navigation