We propose a lexicalized formulation of dependency grammar that addresses both immediate dependence and linear precedence. Our approach distinguishes two orthogonal, yet mutually constraining dependency trees: an ID t...
We propose a lexicalized formulation of dependency grammar that addresses both immediate dependence and linear precedence. Our approach distinguishes two orthogonal, yet mutually constraining dependency trees: an ID tree of syntactic dependencies and a LP tree of topological dependencies. The ID tree is non-ordered, non-projective and its edges are labeled by grammatical functions. The LP tree is ordered and projective and expresses licensed linearizations; its edges are labeled by topological fields. The LP tree can be regarded as deriving from the ID tree through a process of emancipation controlled by lexicalized constraints and principles. In the present article, we formalize valid ID/LP analyses and show how they can be characterized as the solutions of a constraint satisfaction problem. The latter can be solved by constraint programming and forms the basis of our implementation.
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).
Proximity is a key to scalable and meaningful interactions in distributed systems, both natural and artificial, and in particular in pervasive computing environments. However, proximity as such is a vague notion that ...
详细信息
Where is system architecture heading? The special interest group on Computer and systems Architecture (Fachausschuss Rechner- und Systemarchitektur) of the German computer and information technology associations GI an...
详细信息
ISBN:
(数字)9783540247142
ISBN:
(纸本)9783540212386
Where is system architecture heading? The special interest group on Computer and systems Architecture (Fachausschuss Rechner- und Systemarchitektur) of the German computer and information technology associations GI and ITG a- ed this question and discussed it during two Future Workshops in 2002. The result in a nutshell: Everything will change but everything else will remain. Future systems technologies will build on a mature basis of silicon and IC technology,onwell-understoodprogramminglanguagesandsoftwareengineering techniques, and on well-established operating systems and middleware concepts. Newer and still exotic but exciting technologies like quantum computing and DNA processing are to be watched closely but they will not be mainstream in the next decade. Although there will be considerable progress in these basic technologies, is there any major trend which uni?es these diverse developments? There is a common denominator – according to the result of the two - ture Workshops – which marks a new quality. The challenge for future systems technologies lies in the mastering of complexity. Rigid and in?exible systems, built under a strict top-down regime, have reached the limits of manageable complexity, as has become obvious by the recent failure of several large-scale projects. Nature is the most complex system we know, and she has solved the problem somehow. We just haven’t understood exactly how nature does it. But it is clear that systems designed by nature, like an anthill or a beehive or a swarm of birds or a city, are di?erent from today’s technical systems that have beendesignedbyengineersandcomputerscientists.
The emerging hardware support for thread-level speculation opens new opportunities to parallelize sequential programs beyond the traditional limits. By speculating that many data dependences are unlikely during runtim...
详细信息
The emerging hardware support for thread-level speculation opens new opportunities to parallelize sequential programs beyond the traditional limits. By speculating that many data dependences are unlikely during runtime, consecutive iterations of a sequential loop can be executed speculatively in parallel. Runtime parallelism is obtained when the speculation is correct. To take full advantage of this new execution model, a program needs to be programmed or compiled in such a way that it exhibits high degree of speculative thread-level parallelism. We propose a comprehensive cost-driven compilation framework to perform speculative parallelization. Based on a misspeculation cost model, the compiler aggressively transforms loops into optimal speculative parallel loops and selects only those loops whose speculative parallel execution is likely to improve program performance. The framework also supports and uses enabling techniques such as loop unrolling, software value prediction and dependence profiling to expose more speculative parallelism. The proposed framework was implemented on the ORC compiler. Our evaluation showed that the cost-driven speculative parallelization was effective. Our compiler was able to generate good speculative parallel loops in ten Spec2000Int benchmarks, which currently achieve an average 8% speedup. We anticipate an average 15.6% speedup when all enabling techniques are in place.
Multiagent systems have been proposed in the literature as a suitable architectural and implementation approach for cross-enterprise collaboration, due to their support for decentral decision-making and peer-to-peer c...
详细信息
ISBN:
(纸本)9783540790426
Multiagent systems have been proposed in the literature as a suitable architectural and implementation approach for cross-enterprise collaboration, due to their support for decentral decision-making and peer-to-peer coordination, loosely coupled interaction, modeling support for the notion of electronic institutions, and built-in adaptability mechanisms. While we agree with this general view, we argue that different application domain and different market constellations require different types of architecture. In this paper we look at the specific problem of selecting an information and communication technology (ICT) architecture for cross-enterprise business process (CBP) design and enactment. Therefore we identify three important architectural patterns for CBP enactment. We then propose a decision method for architecture selection based on the analytic hierarchy process (AHP) approach. Finally we illustrate the method by applying it to two application scenarios with differing characteristics. Robustness of the decision method is analyzed by performing a sensitivity analysis.
We introduce a first-order language for semantic underspecification that we call Constraint Language for Lambda-Structures (CLLS). A λ-structure can be considered as a λ-term up to consistent renaming of bound varia...
详细信息
Software engineering is an important development task in the automation domain due to the increasing number of embedded systems applied for controlling various system functions. In general, those automation systems ar...
详细信息
Large-scale systems increasingly consist of a mixture of co-dependent software and hardware. The differing nature of software and hardware means that they are often modeled separately and with different approaches. Co...
详细信息
Large-scale systems increasingly consist of a mixture of co-dependent software and hardware. The differing nature of software and hardware means that they are often modeled separately and with different approaches. Comodeling is a design strategy that allows hardware/software integration issues to be identified, investigated and resolved in the early stages of development. Previous work described a comodeling approach that integrates Behavior Engineering with Modelica. This paper revisits this approach and introduces a new means of integration that natively executes Behavior Trees in Modelica rather than utilizing external functions. This enhanced integration has several benefits. Firstly, it makes comodeling easier to apply as the comodel is captured solely in Modelica. Secondly, it makes the ability to execute Behavior Trees widely available. Finally, it opens the possibility to use comodeling with other complementary approaches such as the virtual verification of system designs against system requirements.
暂无评论