scientific article; zbMATH DE number 1142309
From MaRDI portal
Publication:4385525
zbMath0900.68246MaRDI QIDQ4385525
Publication date: 4 May 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (only showing first 100 items - show all)
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ On randomized versus deterministic computation ⋮ On the synchronization of semi-traces ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results ⋮ The Complexity of One-Agent Refinement Modal Logic ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ A split-combination approach to merging knowledge bases in possibilistic logic ⋮ Expressive probabilistic description logics ⋮ Combining answer set programming with description logics for the semantic web ⋮ Outlier detection using default reasoning ⋮ A PTIME-complete matching problem for SLP-compressed words ⋮ A PARALLEL BEST-FIRST B&B ALGORITHM AND ITS AXIOMATIZATION ⋮ Unnamed Item ⋮ On the complexity of graph reconstruction ⋮ The expressive power of unique total stable model semantics ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting ⋮ Expressivity and Complexity of MongoDB Queries ⋮ The complexity of graph connectivity ⋮ Probably approximately optimal satisficing strategies ⋮ The complexity of searching implicit graphs ⋮ Linear constraint query languages expressive power and complexity ⋮ Some rainbow problems in graphs have complexity equivalent to satisfiability problems ⋮ Lower complexity bounds for lifted inference ⋮ Complexity results for answer set programming with bounded predicate arities and implications ⋮ The complexity of counting problems in equational matching ⋮ On the computational complexity of coalitional resource games ⋮ Weak nonmonotonic probabilistic logics ⋮ Complexity and compilability of diagnosis and recovery of graph-based systems ⋮ Voting Procedures, Complexity of ⋮ The complexity of searching succinctly represented graphs ⋮ Unification algorithms cannot be combined in polynomial time ⋮ Unnamed Item ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Unnamed Item ⋮ Belief revision and update: Complexity of model checking ⋮ The computational power of parsing expression grammars ⋮ New tractable classes for default reasoning from conditional knowledge bases ⋮ Strategic Agent Communication: An Argumentation-Driven Approach ⋮ An assessment of numerical techniques to find energy-minimizing microstructures associated with nonconvex potentials ⋮ Computing LOGCFL certificates ⋮ The asymmetric median tree. --- A new model for building consensus trees ⋮ The expressive power of ``possible-is-certain semantics (extended abstract) ⋮ Advocating ownership ⋮ Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete ⋮ The Computational Complexity of Choice Sets ⋮ The Complexity of the Nucleolus in Compact Games ⋮ A uniform tableaux method for nonmonotonic modal logics ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ More results on the complexity of identifying problems in graphs ⋮ Probabilistic logic under coherence: complexity and algorithms ⋮ The complexity of propositional closed world reasoning and circumscription ⋮ Inconsistency-tolerant query answering for existential rules ⋮ Revisiting a result of Ko ⋮ Cumulative default logic: Finite characterization, algorithms, and complexity ⋮ Precise interprocedural dependence analysis of parallel programs ⋮ Finite-state dimension ⋮ Parallel approximation algorithms for maximum weighted matching in general graphs ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ A decision method for nonmonotonic reasoning based on autoepistemic reasoning ⋮ Largest \(j\)-simplices in \(n\)-polytopes ⋮ Multiple total stable models are definitely needed to solve unique solution problems ⋮ On the complexity of partially observed Markov decision processes ⋮ On the computational complexity of graph closures ⋮ On the language of primitive words ⋮ Attribute value reordering for efficient hybrid OLAP ⋮ The expressive powers of stable models for bound and unbound DATALOG queries ⋮ The complexity of concept languages ⋮ The forbidden projections of unate functions ⋮ On randomized versus deterministic computation ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ On the geometric separability of Boolean functions ⋮ Query languages for bags and aggregate functions ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Arity and alternation in second-order logic ⋮ The intrinsic difficulty of recursive functions ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: complexity, algorithms, and implementation ⋮ On the computational cost of disjunctive logic programming: Propositional case ⋮ A refined architecture for terminological systems: Terminology = Schema + Views ⋮ State-variable planning under structural restrictions: algorithms and complexity ⋮ Magic Sets and their application to data integration ⋮ On compact representations of propositional circumscription ⋮ Is intractability of nonmonotonic reasoning a real drawback? ⋮ Queries with arithmetical constraints ⋮ McNaughton families of languages. ⋮ Complexity of some problems in positive and related calculi ⋮ Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms. ⋮ Reducing belief revision to circumscription (and vice versa) ⋮ Semantics and complexity of abduction from default theories ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Rational analysis, intractability, and the prospects of `as if'-explanations ⋮ Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
This page was built for publication:
