About: Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	We prove, in the universe of trees of bounded height, that for any MSO formula with $m$ variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of $m$. This yields a faster MSO model checking algorithm for trees od bounded height than the one for general trees. From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO2) and shrub-depth (MSO1), and thus we give wide generalizations of Lampis' (ESA 2010) and Ganian's (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012). We prove, in the universe of trees of bounded height, that for any MSO formula with $m$ variables there exists a set of kernels such that the size of each of these kernels can be bounded by an elementary function of $m$. This yields a faster MSO model checking algorithm for trees od bounded height than the one for general trees. From that we obtain, by means of interpretation, corresponding results for the classes of graphs of bounded tree-depth (MSO2) and shrub-depth (MSO1), and thus we give wide generalizations of Lampis' (ESA 2010) and Ganian's (IPEC 2011) results. In the second part of the paper we use this kernel structure to show that FO has the same expressive power as MSO1 on the graph classes of bounded shrub-depth. This makes bounded shrub-depth a good candidate for characterization of the hereditary classes of graphs on which FO and MSO1 coincide, a problem recently posed by Elberfeld, Grohe, and Tantau (LICS 2012). (en)
Title	Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences (en)
skos:prefLabel	Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences (en)
skos:notation	RIV/00216224:14330/12:00057865!RIV13-GA0-14330___
http://linked.open...avai/predkladatel	Fakulta informatiky
http://linked.open...avai/riv/aktivita	P S
http://linked.open...avai/riv/aktivity	P(GAP202/11/0196), S
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Hliněný, Petr Gajarský, Jakub
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	136223
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/12:00057865
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	MSO graph property; tree-with; tree-depth; shrub-depth (en)
http://linked.open.../riv/klicoveSlovo	MSO graph property shrub-depth tree-depth tree-with
http://linked.open...ontrolniKodProRIV	[559E353F541D]
http://linked.open...v/mistoKonaniAkce	India
http://linked.open...i/riv/mistoVydani	Dagstuhl, Germany
http://linked.open...i/riv/nazevZdroje	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Well-structured combinatorial classes, width parameters, and design of efficient algorithms
http://linked.open...UplatneniVysledku	2012
http://linked.open...iv/tvurceVysledku	Hliněný, Petr Gajarský, Jakub
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2012-01-01 (xsd:date)
issn	1868-8969
number of pages	12 (xsd:int)
http://bibframe.org/vocab/doi	10.4230/LIPIcs.FSTTCS.2012.112
http://purl.org/ne...btex#hasPublisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS
https://schema.org/isbn	9783939897477
http://localhost/t...ganizacniJednotka	14330
is http://linked.open...avai/riv/vysledek of	Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software