Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Publication
- Publication Type
Articles 1 - 5 of 5
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 …
Finding A Length-Constrained Maximum-Sum Or Maximum-Density Subtree And Its Application To Logistics, Hoong Chuin Lau, Trung Hieu Ngo, Bao Nguyen Nguyen
Finding A Length-Constrained Maximum-Sum Or Maximum-Density Subtree And Its Application To Logistics, Hoong Chuin Lau, Trung Hieu Ngo, Bao Nguyen Nguyen
Research Collection School Of Computing and Information Systems
We study the problem of finding a length-constrained maximum-density path in a tree with weight and length on each edge. This problem was proposed in [R.R. Lin, W.H. Kuo, K.M. Chao, Finding a length-constrained maximum-density path in a tree, Journal of Combinatorial Optimization 9 (2005) 147–156] and solved in O(nU) time when the edge lengths are positive integers, where n is the number of nodes in the tree and U is the length upper bound of the path. We present an algorithm that runs in O(nlog2n) time for the generalized case when the edge lengths are positive real numbers, which …
Estimating Information Amount Under Interval Uncertainty: Algorithmic Solvability And Computational Complexity, Gang Xiang, Olga Kosheleva, George J. Klir
Estimating Information Amount Under Interval Uncertainty: Algorithmic Solvability And Computational Complexity, Gang Xiang, Olga Kosheleva, George J. Klir
Departmental Technical Reports (CS)
In most real-life situations, we have uncertainty: we do not know the exact state of the world, there are several (n) different states which are consistent with our knowledge. In such situations, it is desirable to gauge how much information we need to gain to determine the actual state of the world. A natural measure of this amount of information is the average number of "yes"-"no" questions that we need to ask to find the exact state. When we know the probabilities p1,...,pn of different states, then, as Shannon has shown, this number of questions can be determined as S=-p1 …
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 …