A tableau calculus with automaton-labelled formulae for regular grammar logics

Abstract

We present a sound and complete tableau calculus for the class of regular grammar logics. Our tableau rules use a special feature called automaton-labelled formulae, which are similar to formulae of automaton propositional dynamic logic. Our calculus is cut-free and has the analytic superformula property so it gives a decision procedure. We show that the known EXPTIME upper bound for regular grammar logics can be obtained using our tableau calculus. We also give an effective Craig interpolation lemma for regular grammar logics using our calculus.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 86,273

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

Analytics

Added to PP
2010-05-07

Downloads
27 (#484,001)

6 months
3 (#338,212)

Historical graph of downloads
How can I increase my downloads?