Type and sort conflicts in semantics are usually resolved by a process of reinterpretation, which introduces an operator into the semantic representation. We elaborate on the foundations of a recent approach to reinte...
详细信息
The GOLD Definition Language (GDL) is an Object Oriented (OO) formal specification language for the modeling of multidimensional databases. The OO multidimensional data model called GOLD is based on the OO paradigm, w...
详细信息
Feature trees are the formal basis for algorithms manipulating record like structures in constraint programming, computational linguistics and in concrete applications like software configuration management. Feature t...
详细信息
Feature trees are the formal basis for algorithms manipulating record like structures in constraint programming, computational linguistics and in concrete applications like software configuration management. Feature trees model records, and constraints over feature trees yield extensible and modular record descriptions. We introduce the constraint system FT [less-than or equal to] of ordering constraints interpreted over feature trees. Under the view that feature trees represent symbolic information, the relation less than or equal corresponds to the information ordering ("carries less information than"). We present two algorithms in cubic time, one for the satisfiability problem and one for the entailment problem of FT [less-than or equal to] . We show that FT [less-than or equal to] has the independence property. We are thus able to handle negative conjuncts via entailment and obtain a cubic algorithm that decides the satisfiability of conjunctions of positive and negated ordering constraints over feature trees. Furthermore, we reduce the satisfiability problem of Dorre's weak subsumption constraints to the satisfiability problem of FT [less-than or equal to] and improve the complexity bound for solving weak subsumption constraints from O(n5) to O(n3).
作者：
Chris McDonaldKamran KazemiProgramming
Languages and Systems Group Department of Computer Science The University of Western Australia Nedlands Western Australia 6907
Parallel algorithms are often introduced to students by describing the geometric topologies formed by communicating processes and often the geographic relationships between them. However, the two most common message p...
ISBN:
(纸本)9781581132137
Parallel algorithms are often introduced to students by describing the geometric topologies formed by communicating processes and often the geographic relationships between them. However, the two most common message passing environments used in teaching, PVM and MPI, each provide only rudimentary support for the specification and execution of process topologies. There is a strong need for better syntactic and semantic support for process topologies in these environments, so that students may concentrate on the algorithms being studied, and not have to wrestle with the environments' infrastructure. This paper first motivates, and then describes the use of additional support within PVM and MPI which addresses this need.
Performance prediction is useful in helping parallel programmers answer questions such as speedup scalability. Performance prediction for parallel simulation requires first working out the performance analyzer algorit...
详细信息
We present a constraint system, OF, of feature trees that is appropriate to specify and implement type inference for first-class messages. OF extends traditional systems of feature constraints by a selection constrain...
详细信息
We present a constraint system, OF, of feature trees that is appropriate to specify and implement type inference for first-class messages. OF extends traditional systems of feature constraints by a selection constraint x z, "by first-class feature tree" y, which is in contrast to the standard selection constraint x[f]y, "by fixed feature" f. We investigate the satisfiability problem of OF and show that it can be solved in polynomial time, and even in quadratic time if the number of features is bounded. We compare OF with Treinen's system EF of feature constraints with first-class features, which has an NP-complete satisfiability problem. This comparison yields that the satisfiability problem for OF with negation is NP-hard. Further we obtain NP-completeness, for a specific subclass of OF with negation that is useful for a related type inference problem. Based on OF we give a simple account of type inference for first-class messages in the spirit of Nishimura's recent proposal, and we show that it has polynomial time complexity: We also highlight an immediate extension of this type system that appears to be desirable but makes type inference NP-complete.
As a computational model to be simulated in a DNA computing context, Boolean circuits are especially interesting because of their parallelism. Simulations in concrete biochemical computing settings have been given by ...
详细信息
Entailment of subtype constraints was introduced for constraint simplification in subtype inference systems. Designing an efficient algorithm for subtype entailment turned out to be surprisingly difficult. The situati...
详细信息
暂无评论