About: Faster Existential FO Model Checking on Posets

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

About: Faster Existential FO Model Checking on Posets 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 that the model checking problem for the existen- tial fragment of first order (FO) logic on partially ordered sets is fixed- parameter tractable (FPT) with respect to the formula and the width of a poset (the maximum size of an antichain). While there is a long line of research into FO model checking on graphs, the study of this problem on posets has been initiated just recently by Bova, Ganian and Szeider (LICS 2014), who proved that the existential fragment of FO has an FPT algorithm for a poset of fixed width. We improve upon their result in two ways: (1) the runtime of our algorithm is O(f (\|phi\|, w) · n 2 ) on n-element posets of width w, compared to O(g(\|phi\|) · n h(w) ) of Bova et al., and (2) our proofs are simpler and easier to follow. We comple- ment this result by showing that, under a certain complexity-theoretical assumption, the existential FO model checking problem does not have a polynomial kernel. We prove that the model checking problem for the existen- tial fragment of first order (FO) logic on partially ordered sets is fixed- parameter tractable (FPT) with respect to the formula and the width of a poset (the maximum size of an antichain). While there is a long line of research into FO model checking on graphs, the study of this problem on posets has been initiated just recently by Bova, Ganian and Szeider (LICS 2014), who proved that the existential fragment of FO has an FPT algorithm for a poset of fixed width. We improve upon their result in two ways: (1) the runtime of our algorithm is O(f (\|phi\|, w) · n 2 ) on n-element posets of width w, compared to O(g(\|phi\|) · n h(w) ) of Bova et al., and (2) our proofs are simpler and easier to follow. We comple- ment this result by showing that, under a certain complexity-theoretical assumption, the existential FO model checking problem does not have a polynomial kernel. (en)
Title	Faster Existential FO Model Checking on Posets Faster Existential FO Model Checking on Posets (en)
skos:prefLabel	Faster Existential FO Model Checking on Posets Faster Existential FO Model Checking on Posets (en)
skos:notation	RIV/00216224:14330/14:00074016!RIV15-GA0-14330___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GA14-03501S)
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Obdržálek, Jan Hliněný, Petr Gajarský, Jakub Ordyniak, Sebastian
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	16519
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/14:00074016
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	existential first-order logic; parameterized complexity; kernelization; poset embedding (en)
http://linked.open.../riv/klicoveSlovo	parameterized complexity kernelization existential first-order logic poset embedding
http://linked.open...ontrolniKodProRIV	[C2413A5012E2]
http://linked.open...v/mistoKonaniAkce	Korea
http://linked.open...i/riv/mistoVydani	Berlin
http://linked.open...i/riv/nazevZdroje	ISAAC 2014, LNCS 8889
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	4 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Parameterized algorithms and kernelization in the context of discrete mathematics and logic
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Hliněný, Petr Obdržálek, Jan Ordyniak, Sebastian Gajarský, Jakub
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2014-01-01 (xsd:date)
issn	0302-9743
number of pages	11 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-319-13075-0_35
http://purl.org/ne...btex#hasPublisher	Springer International Publishing
https://schema.org/isbn	9783319130743
http://localhost/t...ganizacniJednotka	14330

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