Elberfeld, Michael
ContextFree Graph Properties via Definable Decompositions
Abstract
Monadicsecond order logic (MSOlogic) is successfully applied in both language theory and algorithm design. In the former, properties definable by MSOformulas are exactly the regular properties on many structures like, most prominently, strings. In the latter, solving a problem for structures of bounded tree width is routinely done by defining it in terms of an MSOformula and applying general formulaevaluation procedures like Courcelle's. The present paper furthers the study of secondorder logics with close connections to language theory and algorithm design beyond MSOlogic.
We introduce a logic that allows to expand a given structure with an existentially quantified tree decomposition of bounded width and test an MSOdefinable property for the resulting expanded structure. It is proposed as a candidate for capturing the notion of "contextfree graph properties" since it corresponds to the contextfree languages on strings, has the same closure properties, and an alternative definition similar to the one of Chomsky and Schützenberger for contextfree languages. Besides studying its languagetheoretic aspects, we consider its expressive power as well as the algorithmics of its satisfiability and evaluation problems.
BibTeX  Entry
@InProceedings{elberfeld:LIPIcs:2016:6557,
author = {Michael Elberfeld},
title = {{ContextFree Graph Properties via Definable Decompositions}},
booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
pages = {17:117:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770224},
ISSN = {18688969},
year = {2016},
volume = {62},
editor = {JeanMarc Talbot and Laurent Regnier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6557},
URN = {urn:nbn:de:0030drops65575},
doi = {10.4230/LIPIcs.CSL.2016.17},
annote = {Keywords: finite model theory, monadic secondorder logic, tree decomposition, contextfree languages, expressive power}
}
2016
Keywords: 

finite model theory, monadic secondorder logic, tree decomposition, contextfree languages, expressive power 
Seminar: 

25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Issue date: 

2016 
Date of publication: 

2016 