Record link: 
http://hdl.handle.net/20.500.12708/152298
-
Title: 
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
en
Citation: 
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 Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1–13). The Association for Computing Machinery. https://doi.org/10.1145/3531130.3533367
-
Publisher DOI: 
10.1145/3531130.3533367
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Bonnet, Édouard 
Dreier, Jan 
Gajarský, Jakub 
Kreutzer, Stephan 
Mählmann, Nikolas 
Simon, Pierre 
Toruńczyk, Szymon 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science 
-
ISBN: 
978-1-4503-9351-5
-
Date (published): 
4-Aug-2022
-
Event name: 
Thirty-Seventh Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 
en
Event date: 
2-Aug-2022 - 5-Aug-2022
-
Event place: 
Haifa, Israel
-
Number of Pages: 
13
-
Publisher: 
The Association for Computing Machinery, New York, USA
-
Peer reviewed: 
Yes
-
Keywords: 
first-order logic; interpretations; locally bounded clique-width; locally bounded treewidth; model checking
en
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
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

90
checked on Nov 21, 2023

Download(s)

2
checked on Nov 21, 2023

Google ScholarTM

Check