Cultural advice

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.

Aboriginal and Torres Strait Islander peoples are advised that ANU Library collections may include images, names, voices, and other representations of deceased persons.

Material in the collection may contain terms, language or views that reflect the period in which the item was created and may be considered inappropriate today.

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

Simple item page
dc.contributor.authorGore, Rajeev
dc.contributor.authorNguyen, Linh Anh
dc.coverage.spatialKoblenz Germany
dc.date.accessioned2015-12-13T22:57:45Z
dc.date.available2015-12-13T22:57:45Z
dc.date.createdSeptember 14-17 2005
dc.date.issued2005
dc.date.updated2015-12-12T07:18:34Z
dc.description.abstractWe 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.
dc.identifier.isbn3540289313
dc.identifier.urihttp://hdl.handle.net/1885/83126
dc.publisherSpringer
dc.relation.ispartofseriesInternational Conference on Theorem Proving with Analytic Tableaux and Related Methods (TABLEAUX 2005)
dc.sourceProceedings of TABLEAUX 2005
dc.subjectKeywords: Automata theory; Decision making; Differentiation (calculus); Automaton-labelled formulae; Craig interpolation lemma; Regular grammar logics; Formal logic
dc.titleA tableau calculus with automaton-labelled formulae for regular grammar logics
dc.typeConference paper
local.bibliographicCitation.lastpage152
local.bibliographicCitation.startpage138
local.contributor.affiliationGore, Rajeev, College of Engineering and Computer Science, ANU
local.contributor.affiliationNguyen, Linh Anh, University of Warsaw
local.contributor.authoruidGore, Rajeev, u9409448
local.description.notesImported from ARIES
local.description.refereedYes
local.identifier.absfor080203 - Computational Logic and Formal Languages
local.identifier.absfor080201 - Analysis of Algorithms and Complexity
local.identifier.ariespublicationMigratedxPub11335
local.identifier.scopusID2-s2.0-33646184790
local.type.statusPublished Version

Downloads

Collections

ANU Research Publications

DSpace software copyright © 2002-2026 LYRASIS