liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
A tableau calculus for regular grammar logics with converse
University of Warsaw.
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
2009 (English)In: Proceedings of the 22nd International Conference on Automated Deduction (CADE), Springer , 2009, Vol. 5663 LNAI, 421-436 p.Conference paper (Refereed)
Abstract [en]

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 [11] 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.

Place, publisher, year, edition, pages
Springer , 2009. Vol. 5663 LNAI, 421-436 p.
Series
, Lecture Notes in Artificial Intelligence, ISSN 0302-9743 ; 5663
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-21208DOI: 10.1007/978-3-642-02959-2_31ISBN: 978-364202958-5OAI: oai:DiVA.org:liu-21208DiVA: diva2:240915
Conference
22nd International Conference on Automated Deduction
Available from: 2009-09-30 Created: 2009-09-30 Last updated: 2011-04-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Szalas, Andrzej
By organisation
KPLAB - Knowledge Processing LabThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 103 hits
ReferencesLink to record
Permanent link

Direct link