Open Access. Powered by Scholars. Published by Universities.®
- Publication
- Publication Type
Articles 1 - 3 of 3
Full-Text Articles in Entire DC Network
The Complexity Of Computing The Size Of An Interval, Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner
The Complexity Of Computing The Size Of An Interval, Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner
Articles
Given a p-order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if (x, y) ∈ A then |x| is polynomially bounded by |y|), an interval size function of A returns, for each string x in the universe, the number of strings in the interval between strings b(x) and t(x) (with respect to A), where b(x) and t(x) are functions that are polynomial-time computable in the length of x. By choosing sets of interval size functions based on feasibility requirements for their underlying p-orders, we obtain new characterizations of complexity classes. We prove that the …
Modal Logic In Computer Science, Leigh Lambert
Modal Logic In Computer Science, Leigh Lambert
Theses
Modal logic is a widely applicable method of reasoning for many areas of computer science. These areas include artificial intelligence, database theory, distributed systems, program verification, and cryptography theory. Modal logic operators contain propositional logic operators, such as conjunction and negation, and operators that can have the following meanings: "it is necessary that," "after a program has terminated," "an agent knows or believes that," "it is always the case that," etc. Computer scientists have examined the difficulty of problems in modal logic, such as satisfiability. Satisfiability determines whether a formula in a given logic is satisfiable. The complexity of satisfiability …
Horn Formula Minimization, Tom Chang
Horn Formula Minimization, Tom Chang
Theses
Horn formulas make up an important subclass of Boolean formulas that exhibits interesting and useful computational properties. They have been widely studied due to the fact that the satisfiability problem for Horn formulas is solvable in linear time. Also resulting from this, Horn formulas play an important role in the field of artificial intelligence. The minimization problem of Horn formulas is to reduce the size of a given Horn formula to find a shortest equivalent representation. Many knowledge bases in propositional expert systems are represented as Horn formulas. Therefore the minimization of Horn formulas can be used to reduce the …