Capturing complexity classes by fragments of second-order logic (Q1193408): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for testing the truth of certain quantified Boolean formulas
+Normal rank
@@ Property / cites work @@
+Henkin quantifiers and complete problems
@@ Property / cites work: Henkin quantifiers and complete problems / rank @@
+Normal rank
@@ Property / cites work @@
+Structure and complexity of relational queries
@@ Property / cites work: Structure and complexity of relational queries / rank @@
+Normal rank
@@ Property / cites work @@
+Horn clause queries and generalizations
@@ Property / cites work: Horn clause queries and generalizations / rank @@
+Normal rank
@@ Property / cites work @@
+Q3775538
@@ Property / cites work: Q3775538 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-time algorithms for testing the satisfiability of propositional horn formulae
+Normal rank
@@ Property / cites work @@
+Q4058132
@@ Property / cites work: Q4058132 / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed-point extensions of first-order logic
@@ Property / cites work: Fixed-point extensions of first-order logic / rank @@
+Normal rank
@@ Property / cites work @@
+Number of quantifiers is better than number of tape cells
+Normal rank
@@ Property / cites work @@
+Upper and lower bounds for first order expressibility
+Normal rank
@@ Property / cites work @@
+Relational queries computable in polynomial time
@@ Property / cites work: Relational queries computable in polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Languages that Capture Complexity Classes
@@ Property / cites work: Languages that Capture Complexity Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic Space is Closed under Complementation
+Normal rank
@@ Property / cites work @@
+Q3830533
@@ Property / cites work: Q3830533 / rank @@
+Normal rank
@@ Property / cites work @@
+Expressibility and Parallel Complexity
@@ Property / cites work: Expressibility and Parallel Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Unification as a complexity measure for logic programming
+Normal rank
@@ Property / cites work @@
+Complete problems for deterministic polynomial time
+Normal rank
@@ Property / cites work @@
+New problems complete for nondeterministic log space
+Normal rank
@@ Property / cites work @@
+The expressive power of stratified logic programs
@@ Property / cites work: The expressive power of stratified logic programs / rank @@
+Normal rank
@@ Property / cites work @@
+The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
+Normal rank
@@ Property / cites work @@
+Descriptive characterizations of computational complexity
+Normal rank
@@ Property / cites work @@
+Symmetric space-bounded computation
@@ Property / cites work: Symmetric space-bounded computation / rank @@
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+The method of forced enumeration for nondeterministic automata
+Normal rank