Publisher Summary This chapter discusses description logics (DLs), which are a family of
logic-based knowledge representation languages that can be used to represent the …

Publisher Summary The past few years have seen enormous progress in the performance of
Boolean satisfiability (SAT) solvers. Despite the worst-case exponential run time of all known …

Description logics (DLs) have a long tradition in computer science and knowledge
representation, being designed so that domain knowledge can be described and so that …

Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …

This newly expanded and updated second edition of the best-selling classic continues to
take the" mystery" out of designing algorithms, and analyzing their efficacy and efficiency …

The problem of deciding whether a given propositional formula in conjunctive normal form is
satisfiable has been widely studied. I t is known that, when restricted to formulas having only …

Many different methods have been devised for automatically verifying finite state systems by
examining state-graph models of system behavior. These methods all depend on decision …

We investigate the complexity of the classical problem of optimal policy computation in
Markov decision processes. All three variants of the problem (finite horizon, infinite horizon …

Among the many approaches to formal reasoning about programs, Dynamic Logic enjoys
the singulax aclv~ ntage of being strongly related to classical logic. Its variants constitute …

Classical complexity theory analyzes and classifies problems by the amount of a resource,
usually time or space, that is required by algorithms solving them. It was a fundamental idea …