A logic programming language based on the Andorra model

The Andorra model is a parallel execution model of logic programs which exploits the dependent and-parallelism and or-parallelism inherent in logic programming. We present a flat subset of a language based on the Andorra model, henceforth called Andorra Prolog, that is intended to subsume both Prolog and the committed choice languages. Flat Andorra, in addition todon’t know anddon’t care nondeterminism, supports control of or-parallel split, synchronisation on variables, and selection of clauses. We show the operational semantics of the language, and its applicability in the domain of committed choice languages. As an examples of the expressiveness of the language, we describe a method for communication between objects by time-stamped messages, which is suitable for expressing distributed discrete event simulation applications. This method depends critically on the ability to expressdon’t know nondeterminism and thus cannot easily be expressed in a committed choice language.     

Energy-centric DVFS controlling method for multi-core platforms

Dynamic voltage and frequency scaling (DVFS) is a well-known and effective technique for reducing energy consumption in modern processors. However, accurately predicting the effect of frequency scaling on system performance is a challenging problem in real environments. In this paper, we propose a realistic DVFS performance prediction method, and a practical DVFS control policy (eDVFS) that aims to minimize total energy consumption in multi-core platforms. We also present power consumption estimation models for CPU and DRAM by exploiting a hardware energy monitoring unit. We implemented eDVFS in Linux, and our evaluation results show that eDVFS can save a substantial amount of energy compared with Linux “on-demand” CPU governor in diverse environments.     

Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation

Given a relation ?? ? ?? × ?? on a set ?? of objects and a set ?? of attributes, the AOC-poset (Attribute/Object Concept poset), is the partial order defined on the “introducers” of objects and attributes in the corresponding concept lattice. In this paper, we present Hermes, a simple and efficient algorithm for building an AOC-poset which runs in O(m i n{n m, n ^α }), where n is the number of objects plus the number of attributes, m is the size of the relation, and n ^α is the time required to perform matrix multiplication (currently α = 2.376). Finally, we compare the runtime of Hermes with the runtime of other algorithms computing the AOC-poset: Ares, Ceres and Pluton. We characterize the cases where each algorithm is the more relevant.     

A note on Moore's interval test for zeros of nonlinear systems

We study relations between Moore's interval test and Miranda's theorem. As an application we combine the (real) Newton iteration with a computational test for Miranda's hypothesis by Moore and Kioustelidis to find an approximate solution to the systemf(x)=0 with specified error bounds.     

Generalized pattern extraction from concept lattices

In this paper, we show how the existence of taxonomies on objects and/or attributes can be used in Formal Concept Analysis to help discover generalized concepts. To that end, we analyze three generalization cases ( ?, ?, and α) and present different scenarios of a simultaneous generalization on both objects and attributes. We also discuss the cardinality of the generalized pattern set against the number of simple patterns produced from the initial data set.     

Parallel algorithms for some functions of two convex polygons

Let P andQ be two convex,n-vertex polygons. We consider the problem of computing, in parallel, some functions ofP andQ whenP andQ are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM havingn ^1/k processors can compute the following functions in O(k^1+?) time: (i) the common tangents betweenP andQ, and (ii) the distance betweenP andQ (and hence a straight line separating them). The positive constant ? can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.     

A Quasi-Newton method with modification of one column per iteration

In this paper we introduce a new Quasi-Newton method for solving nonlinear simultaneous equations. At each iteration only one column ofB _k is changed to obtainB _k+1 . This permits to use the well-known techniques of Linear Programming for modifying the factorization ofB _k . We present a local convergence theorem for a restarted version of the method. The new algorithm is compared numerically with some other methods which were introduced for solving the same kind of problems.     

Puzzle - an efficient,compression independent video encryption algorithm

Real-time video streams require an efficient encryption method to ensure their confidentiality. One of the major challenges in designing a video encryption algorithm is to encrypt the vast amount of video data in real-time to satisfy the stringent time requirements. Video encryption algorithms can be classified according to their association with video compression into joint compression and encryption algorithms and compression-independent encryption algorithms. The latter have a clear advantage over the former regarding the incorporation into existing multimedia systems due to their independence of the video compression. In this paper we present the compression-independent video encryption algorithm Puzzle, which was inspired by the children game jigsaw puzzle. It comprises two simple encryption operations with low computational complexity: puzzling and obscuring. The scheme thereby dramatically reduces the encryption overhead compared to conventional encryption algorithms, such as AES, especially for high resolution video. Further outstanding features of Puzzle are a good trade-off between security demands and encryption efficiency, no impairment on video compression efficiency, and an easy integration into existing multimedia systems. This makes Puzzle particularly well-suited for these security-sensitive multimedia applications, such as videoconferencing, where maximal security and minimal encryption overhead are desired simultaneously.     

Verification of the peak time approach for detection of step initiation using the UTRCEXO

We were able to detect the step initiation for the Unmanned Technology Research Center Exoskeleton before visible movements occurred during the peak time approach. Detection of the step initiation is important for the rapid onset of assistance with the exoskeleton operator’s movement. Many previous studies have attempted to detect the step initiation more rapidly using the precedence walking assistance mechanism with electromyography, or the shadow walking assistance mechanism with the heel-off or toe-off time. In this paper, we detect the step initiation and implement the precedence walking assistance mechanism using the peak time approach. In particular, we detect the vertical ground reaction forces before visible movements occur, which is more reliable, simpler and faster than the previous approaches. We also present insole-type force sensing resistors based on the peak time approach that are used in force plates that can be applied to the Unmanned Technology Research Center Exoskeleton to detect similar events, such as the ground reaction force events, and the step initiation. With the insole-type force sensing resistors, the Unmanned Technology Research Center Exoskeleton can not only detect step initiation before visible movements occur, but can also implement the precedence walking assistance mechanism for step initiation without using any bio-signals.     

Verified inclusion for eigenvalues of the first order PLL equation with general phase detector characteristics

We present a method depending on matrix continued fractions and Sturm's comparison theorem to obtain verified inclusions for eigenvalues of the underlying boundary value problem of the first-order phase locked loop equation $pu'' + (\lambda + \tilde g)u = 0$ ,p = 1/SNR with general phase detector characteristic $\tilde g(\phi )$ .     

P-Prolog: A parallel logic language based on exclusive relation

This paper presents a parallel logic programming language named P-Prolog which is being developed as a logic programming language featuring both and- and or-parallelism. Compared with the other parallel logic programming languages, syntactic constructs such as read-only annotation,⁶⁾ mode declaration²⁾ and communication constraints⁷⁾ are not used in P-Prolog. A new concept introduced in P-Prolog is the exclusive relation of guarded Horn clauses. Advances included in P-prolog. are:

1. The synchronization mechanism can determine the direction of data flow dynamically.
2. Guarded Horn clauses can be interpreted as eitherdon’t care nondeterminism ordon’t know non-determinism.

A prototype interpreter of P-Prolog has been implemented in C-Prolog. We are now implementing a P-Prolog interpreter in the C language.     

Logical diagnosis ofLDL programs

The debuggers of Ref. 11) and most of their derivatives are of themeta-interpreter type. The computation of the debugger tracks the computation of the program to be diagnosed at the level of procedure call. This is adequate if the intuitive understanding of the programmer is in terms of procedure calls; as is indeed the case in Prolog. InLDL however, while the semantics of the language are described in a bottom-up, fixpoint model of computation,⁸⁾ theactual execution of a program is a complex sequence of low-level procedure calls determined (and optimized) by the compiler. Consequently, a trace of these procedure calls is of little use to the programmer. Further, one cannot “execute” anLDL program as if it was a Prolog program; the program may simply not terminate in its Prolog reading and severalLDL constructs have no obvious Prolog counterparts. We identify the origin of a fault in theLDL program by a top-down, query/subquery approach. The basic debugger, implemented in Prolog, is a shell program between the programmer and theLDL program: it poses queries and uses the results to drive the interaction with the user. It closely resembles the one presented in Ref. 11). The core of a more sophisticated debugger is presented as well. Several concepts are introduced in order to quantify debugging abilities. One is that of agenerated interpretation, in which the structureless intended interpretation of Ref. 11) is augmented with causality. Another is the (idealized) concept of areliable oracle. We show that given an incorrect program and a reliable oracle which uses a generated interpretation, a cause for the fault will be found in finitely many steps. This result carries over to the more sophisticated debugger.     

Finding a minimal cover for binary images: An optimal parallel algorithm

Given a black-and-white image, represented by an array of √n × √n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in [logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.     

Program invariants as fixedpoints

We argue that soundness and relative completeness theorems for Floyd-Hoare Axiom Systems ([3], [5], [18]) are really fixedpoint theorems. We give a characterization of program invariants as fixedpoints of functionals which may be obtained in a natural manner from the text of a program. We show that within the framework of this fixedpoint theory, soundness and relative completeness results have a particularly simple interpretation. Completeness of a Floyd-Hoare Axiom System is equivalent to the existence of a fixedpoint for an appropriate functional, and soundness follows from the maximality of this fixedpoint. The functionals associated with regular procedure declarations are similar to thepredicate transformers of Dijkstra; for nonregular recursions it is necessary to use a generalization of the predicate transformer concept which we call arelational transformer.     

Simulations among concurrent-write PRAMs

This paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [G], and the COMMON PRAM [K]. Improving the trivial and seemingly optimalO(logn) simulation, we show that one step of a PRIORITY machine can be simulated byO(logn/(log logn)) steps of a COMMON machine with the same number of processors (and more memory). We further prove that this is optimal, if processor communication is restricted in a natural way.     

Probabilistic analysis of a grouping algorithm

We study thegrouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence ofn numbers drawn from {0,1, 2,...,m?1} with repetitions allowed; we are to rearrange them, using as few swaps of adjacent elements as possible, into an order such that all the like numbers are grouped together. It is known that this problem is NP-hard. We present a probabilistic analysis of a grouping algorithm calledMEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior ofMEDIAN is within 10% of optimal and is asymptotically optimal asn/m→∞ or asn/m→0.     

Parallel complexity of logical query programs

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the “polynomial fringe property,” this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the “linear” and “piecewise linear” classes of logic programs are inN C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an “elementary chain.” We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the “polynomial fringe property;” hence such programs are inN C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.