Paper Info
Title
Parameterized Complexity of Some Prefix-Vocabulary Fragments of First-Order Logic.
Abstract
We analyze the parameterized complexity of the satisfiability problem for some prefix-vocabulary fragments of First-order Logic with the finite model property. Here we examine three natural parameters: the quantifier rank, the vocabulary size and the maximum arity of relation symbols. Following the classical classification of decidable prefixvocabulary fragments, we will see that, for all relational classes of modest complexity and some classical classes, fixed-parameter tractability is achieved by using the above cited parameters.
Year
DOI
Venue
2018
10.1007/978-3-662-57669-4_9
Lecture Notes in Computer Science
Keywords
Field
DocType
Satisfiability,Prefix-vocabulary fragments of first-order logic,Fixed-parameter tractability
Discrete mathematics,Parameterized complexity,Arity,Computer science,Satisfiability,Boolean satisfiability problem,Decidability,Prefix,Theoretical computer science,First-order logic,Vocabulary
Conference
Volume
ISSN
Citations 
10944
0302-9743
0
PageRank 
References 
Authors
0.34
9
3
Name
Order
Citations
PageRank
Luis Henrique Bustamante151.09
Ana Teresa Martins224.80
Francicleber Ferreira Martins300.34