scientific article; zbMATH DE number 7136657

DOI10.23638/LMCS-15(3:31)2019zbMath1494.68164arXiv1703.01860MaRDI QIDQ4972729

Yijia Chen, Michael Elberfeld, Moritz Müller

Publication date: 26 November 2019

Full work available at URL: https://arxiv.org/abs/1703.01860

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

model checkingparameterized logarithmic spacebounded-variable first-order logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Machine-based methods in parameterized complexity theory
• Tree-size bounded alternation
• Upper and lower bounds for first order expressibility
• Properties that characterize LOGCFL
• Space-efficient recognition of sparse self-reducible languages
• Conjunctive-query containment and constraint satisfaction
• Corrigendum to: ``Advice classes of parameterized tractability
• Describing parameterized complexity classes
• Parameterized random complexity
• On the space and circuit complexity of parameterized problems: classes and completeness
• Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
• Parametrized complexity theory.
• On the structure of parameterized problems in NP
• Relationships between nondeterministic and deterministic tape complexities
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Fixed-Parameter Tractability, Definability, and Model-Checking
• The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space
• Bounded Variable Logic, Parameterized Logarithmic Space, and Savitch’s Theorem
• Computing Hitting Set Kernels By AC^0-Circuits
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Nondeterministic Space is Closed under Complementation
• Two Applications of Inductive Counting for Complementation Problems
• One Hierarchy Spawns Another
• Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
• Bounds on Monotone Switching Networks for Directed Connectivity
• Deciding First-Order Properties of Nowhere Dense Graphs
• Algorithmic Meta Theorems for Sparse Graph Classes
• The complexity of graph connectivity
• Tree-depth, quantifier elimination, and quantifier rank
• When is the evaluation of conjunctive queries tractable?
• Computational Complexity
• On the complexity of existential positive queries

This page was built for publication: