FO Model Checking of Interval Graphs

FO Model Checking of Interval Graphs

We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that FO model checking and successor-invariant FO model checking can be solved in time O(n log n) for n-vertex interval grap...

Bibliográfalaš dieđut
Váldodahkkit:	Robert Ganian, Petr Hlineny, Daniel Kral, Jan Obdrzalek, Jarett Schwartz, Jakub Teska
Materiálatiipa:	Artihkal
Giella:	English
Almmustuhtton:	Logical Methods in Computer Science e.V. 2015-12-01
Ráidu:	Logical Methods in Computer Science
Fáttát:	computer science - discrete mathematics computer science - logic in computer science
Liŋkkat:	https://lmcs.episciences.org/1612/pdf

Geahča maid

Faster Existential FO Model Checking on Posets
Dahkki: Jakub Gajarský, et al.
Almmustuhtton: (2015-12-01)

Shrub-depth: Capturing Height of Dense Graphs
Dahkki: Robert Ganian, et al.
Almmustuhtton: (2019-01-01)

Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences
Dahkki: Jakub Gajarsky, et al.
Almmustuhtton: (2015-04-01)

Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs
Dahkki: Berit Grußien
Almmustuhtton: (2019-07-01)

Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
Dahkki: Jan Dreier
Almmustuhtton: (2023-06-01)

Model Checking Lower Bounds for Simple Graphs
Dahkki: Michael Lampis
Almmustuhtton: (2014-03-01)

Efficient enumeration of non-isomorphic interval graphs
Dahkki: Patryk Mikos
Almmustuhtton: (2021-03-01)

Deciding definability in FO2(<h,<v) on trees
Dahkki: Thomas Place, et al.
Almmustuhtton: (2015-09-01)

Monadic second-order definable graph orderings
Dahkki: Achim Blumensath, et al.
Almmustuhtton: (2014-01-01)

Pebble Games, Proof Complexity, and Time-Space Trade-offs
Dahkki: Jakob Nordstrom
Almmustuhtton: (2013-09-01)

Asymptotically almost all \lambda-terms are strongly normalizing
Dahkki: René David, et al.
Almmustuhtton: (2013-02-01)

Twin-width and permutations
Dahkki: Édouard Bonnet, et al.
Almmustuhtton: (2024-07-01)

Correct and Efficient Antichain Algorithms for Refinement Checking
Dahkki: Maurice Laveaux, et al.
Almmustuhtton: (2021-02-01)

Interface Modeling for Quality and Resource Management
Dahkki: Martijn Hendriks, et al.
Almmustuhtton: (2021-05-01)

Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption
Dahkki: Laura Bozzelli, et al.
Almmustuhtton: (2022-02-01)

On the End-Vertex Problem of Graph Searches
Dahkki: Jesse Beisegel, et al.
Almmustuhtton: (2019-06-01)

Semipaired Domination in Some Subclasses of Chordal Graphs
Dahkki: Michael A. Henning, et al.
Almmustuhtton: (2021-07-01)

Connection Matrices and the Definability of Graph Parameters
Dahkki: Tomer Kotek, et al.
Almmustuhtton: (2014-10-01)

Universal Horn Sentences and the Joint Embedding Property
Dahkki: Manuel Bodirsky, et al.
Almmustuhtton: (2022-05-01)

Using models to model-check recursive schemes
Dahkki: Sylvain Salvati, et al.
Almmustuhtton: (2015-06-01)

Boolean proportions
Dahkki: Christian Antić
Almmustuhtton: (2024-04-01)

Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
Dahkki: Fábio Protti, et al.
Almmustuhtton: (2018-11-01)

On almost hypohamiltonian graphs
Dahkki: Jan Goedgebeur, et al.
Almmustuhtton: (2019-07-01)

Path Checking for MTL and TPTL over Data Words
Dahkki: Shiguang Feng, et al.
Almmustuhtton: (2017-09-01)

Type-checking Liveness for Collaborative Processes with Bounded and Unbounded Recursion
Dahkki: Søren Debois, et al.
Almmustuhtton: (2016-01-01)

Counterexample-Guided Prophecy for Model Checking Modulo the Theory of Arrays
Dahkki: Makai Mann, et al.
Almmustuhtton: (2022-08-01)

Equivalence of the filament and overlap graphs of subtrees of limited trees
Dahkki: Jessica Enright, et al.
Almmustuhtton: (2017-06-01)

Positive First-order Logic on Words and Graphs
Dahkki: Denis Kuperberg
Almmustuhtton: (2023-07-01)

Effective zero-dimensionality for computable metric spaces
Dahkki: Robert Kenny
Almmustuhtton: (2015-03-01)

Optimizing tree decompositions in MSO
Dahkki: Mikołaj Bojańczyk, et al.
Almmustuhtton: (2022-02-01)

The parameterized space complexity of model-checking bounded variable first-order logic
Dahkki: Yijia Chen, et al.
Almmustuhtton: (2019-09-01)

Products of effective topological spaces and a uniformly computable Tychonoff Theorem
Dahkki: Robert Rettinger, et al.
Almmustuhtton: (2013-11-01)

Bifinite Chu Spaces
Dahkki: Manfred Droste, et al.
Almmustuhtton: (2010-01-01)

Universal Structures and the logic of Forbidden Patterns
Dahkki: Florent R. Madelaine
Almmustuhtton: (2009-06-01)

Weakly toll convexity and proper interval graphs
Dahkki: Mitre C. Dourado, et al.
Almmustuhtton: (2024-04-01)

Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
Dahkki: Márcia R. Cappelle, et al.
Almmustuhtton: (2022-02-01)

Towards an Algebra for Cascade Effects
Dahkki: Elie M. Adam, et al.
Almmustuhtton: (2017-07-01)

Partial Model Checking using Networks of Labelled Transition Systems and Boole an Equation Systems
Dahkki: Frédéric Lang, et al.
Almmustuhtton: (2013-10-01)

Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
Dahkki: Arman Boyacı, et al.
Almmustuhtton: (2018-01-01)

Bounded Quantifier Instantiation for Checking Inductive Invariants
Dahkki: Yotam M. Y. Feldman, et al.
Almmustuhtton: (2019-08-01)