A tableau calculus for regular grammar logics with converse
2009 (English)In: Proceedings of the 22nd International Conference on Automated Deduction (CADE), Springer, 2009, Vol. 5663 LNAI, 421-436Conference paper (Refereed)
We give a sound and complete tableau calculus for deciding the general satisfiability problem of regular grammar logics with converse (REG c logics). Tableaux of our calculus are defined as "and-or" graphs with global caching. Our calculus extends the tableau calculus for regular grammar logics given by Goré and Nguyen  by using a cut rule and existential automaton-modal operators to deal with converse. We use it to develop an ExpTime (optimal) tableau decision procedure for the general satisfiability problem of REG c logics. We also briefly discuss optimizations for the procedure.
Lecture Notes in Artificial Intelligence, ISSN 0302-9743 ; 5663
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-21208DOI: 10.1007/978-3-642-02959-2_31ISBN: 978-364202958-5OAI: oai:DiVA.org:liu-21208DiVA: diva2:240915
22nd International Conference on Automated Deduction