1,721,131 research outputs found
Circumscribing datalog: expressive power and complexity
No full textAbstractIn this paper we study a generalization of datalog, the language of function-free definite clauses. It is known that standard datalog semantics (i.e., least Herbrand model semantics) can be obtained by regarding programs as theories to be circumscribed with all predicates to be minimized. The extension proposed here, called datalogcirc, consists in considering the general form of circumscription, where some predicates are minimized, some predicates are fixed, and some vary. We study the complexity and the expressive power of the language thus obtained. We show that this language (and, actually, its non-recursive fragment) is capable of expressing all the queries in DB-co-NP and, as such, is much more powerful than standard datalog, whose expressive power is limited to a strict subset of PTIME queries. Both data and combined complexities of answering datalogcirc queries are studied. Data complexity is proved to be co-NP-complete. Combined complexity is shown to be in general hard for co-NE and complete for co-NE in the case of Herbrand bases containing k distinct constant symbols, where k is bounded
Algorithms for Graph and Network Analysis: Graph Alignment
No full textIn this article we discuss the problem of graph alignment, which has been longly referred to for the purpose of analyzing and comparing biological networks. In particular, we describe different facets of graph alignment, according to the number of input networks, the fixed output objective, the possible heterogeneity of input data. Accordingly, we will discuss pairwise and multiple alignment, global and local alignment, etc. Moreover, we provide a comprehensive overview of the algorithms and techniques proposed in the literature to solve each of the specific considered types of graph alignment. In order to make the material presented here complete and useful to guide the reader in the use of the alignment algorithms, we also illustrate available software tools implementing some of the techniques proposed in the literature. Finally, we discuss the main emerging research directions on this topic
Symbolic Computation of Schedulability Regions Using Parametric Timed Automata
No full textIn this paper, we address the problem of symbolically computing the region in the parameter`s space that guarantees a feasible schedule, given a set of real-time tasks characterised by a set of parameters and by an activation pattern. We make three main contributions. First, we propose a novel and general method, based on parametric timed automata. Second, we prove that the algorithm terminates for the case of periodic processes with bounded offsets. Third, we provide an implementation based on the use of symbolic model checking techniques for parametric timed automata, and present some case studies
Algorithms for selective enumeration of prime implicants
No full textWe present a new approach for selective enumeration of prime implicants of CNF formulae. The method uses a 0-1 programming schema, having feasible solutions corresponding to prime implicants. Prime implicants are generated one at a rime, so that as many of them can be computed as needed by the specific application considered. Selective generation is also supported, whereby preferences on the structure of generated prime implicants can be specified. We present two algorithms for selective enumeration of prime implicants and discuss their properties. The former amounts to solving the basic 0-1 programming schema first, to obtain an implicant psi' (not necessarily a prime one), and then generating a prime implicant implied by psi'. The latter is based on adding a suitable minimization function to the basic 0-1 programming schema so that finding optimal solutions corresponds one-to-one to generating prime implicants of the original theory. We show that the latter algorithm has wider applicability but is less efficient than the former one. Finally we present experimental results, which confirm the effectiveness of our approach in computing prime implicants of CNF formulae. (C) 1999 Elsevier Science B.V. All rights reserved
NP-SPEC: An Executable Specification Language for Solving all Problems in NP
No full textthis paper we present the executable specification language np-spec, which allows the user to specify exactly all problems which belong to the complexity class NP
- …
