46388294
Soft Sorting in Logic Programming
Integrating sorts (types) into logic programming languages increases their expressiveness and evaluation efficiency. The sort structures usually considered are strict, in the sense that whenever an expression has a subexpression which is not properly sorted, the expression is classified as ill-sorted, and in effect is regarded as meaningless. Typically a logic programming language with strict sorting is incomplete, in the sense that some intuitively meaningful programs and queries are ill-sorted and hence are not part of the language.
36856498
Defining Soft Sortedness by Abstract Interpretation
Sorted languages can improve the expressiveness and efficiency of reasoning. A conventional sorted language typically includes well-sortedness rules amongst the rules for well-formedness. A major disadvantage of this approach is that many intuitively meaningful expressions are ill-sorted and hence not part of the language.
18066023
Improvement on vertex cover for low-degree graphs
The Vertex Cover problem (given a graph G and an integer k, decide if G has a vertex cover of k vertices) is one of the six “basic” NP-complete problems according to Garey and Johnson [7]. It is fixed-parameter tractable in terms of Downey and Fellows [5], that is, it can be solved in time O(f(k)n), where f is a function of the parameter k but independent of the input length n and c is a constant independent of the parameter k. Continuous efforts have been made in improving fixed-parameter tractable algorithms for the vertex cover problem, starting from Buss’ algorithm of running time O(kn + 2kk2k+2) [2]. Downey and Fellows [4] developed an O(kn + 2kk2) time algorithm. More recently, Balasubramanian et al. [1] developed an O(kn+1.3247kk2) time algorithm. Later Downey et al. [6] improved the result slightly to time complexity O(kn + 1.3195kk2), and Niedermeier and Rossmanith [9] developed an algorithm of time O(kn+1.2918kk2). More recently, Chen et al. [3] developed an O(kn + 1.271kk2) time algorithm. For the restricted version of the vertex
17449226
Approximation algorithms for scheduling multiple feasible interval jobs
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both nonpreemptible and preemptible jobs. This paper develops two approximation algorithms for nonpreemptible and preemptible jobs. When jobs are nonpreemptible, algorithm LECF is with a 2-approximation factor; when jobs are preemptible, algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.
5642826
A garbage-collecting typed assembly language
Typed assembly languages usually support heap allocation safely, but often rely on an external garbage collector to deallocate objects from the heap and prevent unsafe dangling pointers. Even if the external garbage collector is provably correct, verifying the safety of the interaction between TAL programs and garbage collection is nontrivial. This paper introduces a typed assembly language whose type system is expressive enough to type-check a Cheney-queue copying garbage collector, so that ordinary programs and garbage collection can co-exist and interact inside a single typed language. The only built-in types for memory are linear types describing individual memory words, so that TAL programmers can define their own object layouts, method table layouts, heap layouts, and memory management techniques.
30548729
A Class of Stratified Programs in Autoepistemic Logic of Knowledge and Belief
Przymusinski proposed [11] AELB, the autoepistemic logic of knowledge and belief. The AELB logic is a very powerful and expressive formal system which isomorphically contains various major non-monotonic knowledge representation formalisms and major logic program semantics. Thus AELB can be used as a unifying framework for non-monotonic knowledge representation formalisms, which allows us to compare and better understand different formalizations of common-sense knowledge.
19987062
On the construction of most reliable networks
The construction of most reliable networks is investigated. In particular, the study of restricted edge connectivity shows that general Harary graphs are max λ-min mi for all i=λ, λ+1,....2λ- 3. As a consequence, this implies that for each pair of positive integers n and e, there is a graph of n vertices and e edges that is max λ-min mi for all i= λ,λ + 1,....2λ - 3. General Harary graphs that are max λ-min mi for all i= λ, λ + 1,.... 2λ - 2 are also constructed.