1,720,975 research outputs found
A parallel on-line algorithm for deriving all logical conclusions implied by a set of binary relations
No full text
Adamant digraphs
No full textAbstractIn this paper we introduce the class of adamant digraphs. These are the digraphs with the property that for any two vertices x and y, the set of successors of x and the set of successors of y are either disjoint or (inclusionwise) comparable. Those adamant digraphs whose inverse digraph is also adamant are called inflexible. This subclass includes many previously known classes, e.g. minimal series-parallel digraphs and Ferrers digraphs. For both adamant and inflexible digraphs we give alternative characterizations and linear-time recognition algorithms. The special case of symmetric adamant digraphs is investigated
Deux modules de traitements des maillages: Module Q4T-Module MODGE
No full textThe MODULEF library contains about 3000 procedures written in Fortran 77. These procedures were designed with the utmost concern for software portability
Un module de maillage semi automatique: QCOURB
No full textThe MODULEF library contains about 3000 procedures written in Fortran 77. These procedures were designed with the utmost concern for software portability
Introduzione al progetto logico di un calcolatore digitale
No full textIntroduzione al progetto logico di un calcolatore digital
On line 2- satisfiability
No full textWe deal with the followingon-line 2-satisfiability problemP(m, n): starting fromC(0)=true, consider a sequence ofm Boolean formulasC(k) (inn variables and in conjunctive normal form), each of them being the intersection of the previous one with a single clause which is the union of two literals. Solve the sequence of 2-satisfiability problemsC(k)=true,k=1,...,m. It is well known that a 2-satisfiability problem involvingm clauses can be solved inO(m) time. Thus, by a naive approach one can solveP(m, n) in overallO(m 2) time. We present an algorithm with overallO(nm) time complexity, which for every formula not only checks its satisfiability, but also actually computes a solution (if any), and moreover, detects all forced and all identical variables. Our algorithm makes use of an efficient on-line transitive closure procedure by Italiano. We discuss two applications to the design of integrated electronic circuits and to edge classification in automated perception
- …
