We consider the problem of solving linear equations over various semirings. In particular, solving of linear equations over polynomial rings with the additional restriction that the solutions must have only non-negati...
详细信息
We consider the problem of solving linear equations over various semirings. In particular, solving of linear equations over polynomial rings with the additional restriction that the solutions must have only non-negative coefficients is shown to be undecidable. Applications to undecidability proofs of several unification problems are illustrated, one of which, unification modulo one associative-commutative function and one endomorphism, has been a long-standing open problem. The problem of solving multiset constraints is also shown to be undecidable.
Building large, heterogeneous, distributed software systems poses serious problems for the software engineer;achieving interoperability of software systems is still a major challenge. We describe an experiment in desi...
详细信息
The notion of "time" plays an important role when coordinating large, heterogeneous, distributed software systems. We present a generic coordination architecture that supports relative and absolute, discrete...
详细信息
It is well known that extracting parallel loops plays a significant role in designing parallelizing compilers. The execution efficiency of a loop is enhanced when the loop can be executed in parallel or partial parall...
详细信息
ISBN:
(纸本)0818672676
It is well known that extracting parallel loops plays a significant role in designing parallelizing compilers. The execution efficiency of a loop is enhanced when the loop can be executed in parallel or partial parallel, like a DOALL or DOACROSS loop. This paper reports on the practical parallelism detector (PPD) that is implemented in PFPC (a portable FORTRAN parallelizing compiler running on OSF/1) at NCTU to concentrate on finding the parallelism available in loops. The PPD can extract the potential DOALL and DOACROSS loops in a program by invoking a combination of the ZIV test and the I test for verifying array subscripts. Furthermore, if DOACROSS loops are available, an optimization of synchronization statement is made. Experimental results show that PPD is more reliable and accurate than previous approaches.
We goal of the work is to derive four-voice music pieces from given musical plans, which describe the harmonic flow and the intentions of a desired composition. We developed the experimentation platform COMPOzE for in...
详细信息
We goal of the work is to derive four-voice music pieces from given musical plans, which describe the harmonic flow and the intentions of a desired composition. We developed the experimentation platform COMPOzE for intention based composition. COMPOzE is based on constraint programming over finite domains of integers. We argue that constraint programming provides a suitable technology for this task and that the libraries and tools available for the constraint programming system Oz effectively support the implementation of COMPOzE. This work links the research areas of automatic music composition on one hand and finite domain constraint programming on the other, and contributes the tool COMPOzE, which practically demonstrates the potential of constraint programming to open up new areas of application for automatic music composition.
Although precedences are often used to resolve ambiguities in programming language descriptions, there has been no parser-independent definition of languages which are generated by grammars with precedence rules. This...
Although precedences are often used to resolve ambiguities in programming language descriptions, there has been no parser-independent definition of languages which are generated by grammars with precedence rules. This paper gives such a definition for a subclass of context-free grammars. The definition is shown to be equivalent to the implicit definition an operator precedence parser gives. A problem with a language containing infix, prefix and postfix operators of different precedences is that the well-known algorithm, which transforms a grammar with infix operator precedences to an ordinary unambiguous context-free grammar, does not work. This paper gives an algorithm that works also for prefix and postfix operators, and the correctness of it is proved. An application of the algorithm is also presented.
In this paper we show that the critical part of a correctness proof for implementations of higher-order functional languages is amenable to machine-assisted proof. An extended version of the lambda-calculus is conside...
详细信息
ISBN:
(纸本)3540600175
In this paper we show that the critical part of a correctness proof for implementations of higher-order functional languages is amenable to machine-assisted proof. An extended version of the lambda-calculus is considered, and the congruence between its direct and continuation semantics is proved. The proof has been constructed with the help of a generic theorem prover - Isabelle. The major part of the problem lies in establishing the existence of predicates which describe the congruence. This has been solved using Milne's inclusive predicate strategy [5]. The most important intermediate results and the main theorem as derived by Isabelle are quoted in the paper.
For finite convergent term-rewriting systems the equational unification problem is shown to be recursively independent of the equational matching problem, the word matching problem, and the (simultaneous) 2nd-order eq...
详细信息
We address the problem of performing a pipelined broadcast on a mesh architecture. Meshes require a different approach than other topologies, and their very nature puts a tighter bound on the performance that one can ...
详细信息
We address the problem of performing a pipelined broadcast on a mesh architecture. Meshes require a different approach than other topologies, and their very nature puts a tighter bound on the performance that one can hope to achieve. By using the appropriate techniques, however, one can obtain excellent performance for sufficiently long messages. The resulting algorithm will work on meshes of any dimension with any number of nodes. Our model assumes that the mesh is a torus and/or that it has bidirectional links and uses wormhole routing. Performance data from the Cray T3D are included.
暂无评论