descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 05 Jul 2016Embargo end date: 01 Jan 2016Publisher:ACMJournal:Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer ScienceFunded by:EC | LIPA

Authors: Bojańczyk, Mikołaj; Pilipczuk, Michał;

doi: 10.1145/2933575.2934508 , 10.48550/arxiv.1605.03045

arXiv: 1605.03045

Definability equals recognizability for graphs of bounded treewidth

- Summary
- Subjects
- Metrics

Abstract

We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is recognizable in the following sense: constant-width tree decompositions of graphs satisfying the property can be recognized by tree automata. While the forward implication is a classic fact known as Courcelle's theorem, the converse direction remained open

21 pages, an extended abstract will appear in the proceedings of LICS 2016

Related Organizations

University of Warsaw
Poland

Keywords

FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Computational Complexity (cs.CC), Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Computer Science - Discrete Mathematics

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	14
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%