<div class="csl-bib-body">
<div class="csl-entry">Bonnet, É., Dreier, J., Gajarský, J., Kreutzer, S., Mählmann, N., Simon, P., & Toruńczyk, S. (2022). Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. In <i>Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 1–13). The Association for Computing Machinery. https://doi.org/10.1145/3531130.3533367</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/152298
-
dc.description.abstract
An interpretation is an operation that maps an input graph to an output graph by redefning its edge relation using a frst-order formula. This rich framework includes operations such as taking the complement or a fxed power of a graph as (very) special cases. We prove that there is an FPT algorithm for the frst-order model checking problem on classes of graphs which are frst-order interpretable in classes of graphs with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and of classes of bounded genus in general. To obtain this result we develop a new tool which works in a very general setting of NIP classes and which we believe can be an important ingredient in obtaining similar results in the future.
en
dc.language.iso
en
-
dc.subject
first-order logic
en
dc.subject
interpretations
en
dc.subject
locally bounded clique-width
en
dc.subject
locally bounded treewidth
en
dc.subject
model checking
en
dc.title
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
CNRS Délégation Rhône-Auvergne
-
dc.contributor.affiliation
University of Warsaw, Poland
-
dc.contributor.affiliation
Technische Universität Berlin, Germany
-
dc.contributor.affiliation
University of Bremen, Germany
-
dc.contributor.affiliation
University of California, Berkeley, United States of America (the)
-
dc.contributor.affiliation
University of Warsaw, Poland
-
dc.relation.isbn
978-1-4503-9351-5
-
dc.description.startpage
1
-
dc.description.endpage
13
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
-
tuw.relation.publisher
The Association for Computing Machinery
-
tuw.relation.publisherplace
New York, USA
-
tuw.book.chapter
54
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1145/3531130.3533367
-
dc.description.numberOfPages
13
-
tuw.author.orcid
0000-0002-1653-5822
-
tuw.author.orcid
0000-0003-3657-7736
-
tuw.author.orcid
0000-0002-1130-9033
-
tuw.event.name
Thirty-Seventh Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
en
tuw.event.startdate
02-08-2022
-
tuw.event.enddate
05-08-2022
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Haifa
-
tuw.event.country
IL
-
tuw.event.presenter
Bonnet, Édouard
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openairetype
conference paper
-
item.fulltext
no Fulltext
-
item.languageiso639-1
en
-
item.grantfulltext
restricted
-
item.cerifentitytype
Publications
-
crisitem.author.dept
CNRS Délégation Rhône-Auvergne
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
