Parameterized complexity of fixed variable logics

DOI10.4230/LIPICS.FSTTCS.2014.109MaRDI QIDQ2978506zbMATH OpenOpenAlexFDO

Authors Christoph Berkholz, Michael Elberfeld

Publication date 25 April 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2014.109

zbMATH Keywords

first-order logicparameterized complexitypebble gamespolynomial spaceregular resolutions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• The parameterized space complexity of model-checking bounded variable first-order logic
• First-Order Model Checking Problems Parameterized by the Model
• Fixed-parameter tractability, definability, and model-checking
• scientific article; zbMATH DE number 1424025
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic

Cited in

(8)

• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• Bounded variable logic, parameterized logarithmic space, and Savitch's theorem
• Parameterized Complexity Classes under Logical Reductions
• First-Order Model Checking Problems Parameterized by the Model
• The parameterized space complexity of model-checking bounded variable first-order logic
• Parameterized Parallel Computing and First-Order Logic
• Complexity of fixed-size bit-vector logics
• Variant Satisfiability of Parameterized Strings

This page was built for publication: Parameterized complexity of fixed variable logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978506)