首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
The NValue constraint counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.  相似文献   

2.
The last decade progresses have led the Satisfiability Problem (sat) to be a great and competitive practical approach to solve a wide range of industrial and academic problems. Thanks to these progresses, the size and difficulty of the sat instances has grown significantly. Among the recent solvers, a few are parallel and most of them use the message passing paradigm. In a previous work by Vander-Swalmen et al. (IWOMP, 146–157, 2008), we presented a fine grain parallel sat solver designed for shared memory using OpenMP and named mtss, for Multi Threaded Sat Solver. mtss extends the “guiding path” notion and uses a collaborative approach where a rich thread is in charge of the search-tree evaluation and where a set of poor threads yield logical or heuristics information to simplify the rich task. In this paper, we extend the poor thread abilities of mtss and present extensive comparative results on random 3-sat problems. These new experimentations show that fine grained techniques associated to poor tasks within the framework of mtss can achieve very interesting speedup on multi-core processors.  相似文献   

3.
The collaborative editing of documents is a very common task nowadays. Writing groups are often distributed over many locations because of the globalization of organizations and the increasing interdisciplinarity of tasks. Since many writers already use computers for their jobs, providing computer support for the collaborative writing process has been identified as an important goal. Numerous tools for computer supported collaborative writing have already emerged but in most cases have not come into widespread usage. In this article the requirements of users for a collaborative editor are analyzed. Providing as much flexibility as possible to the users is identified as a basic need. According to the requirements summary a model for a group editing environment is presented. The model covers cooperative work in local and wide area networks using synchronous and asynchronous cooperation. Finally, an application of the model is presented in the form of the multi-user editing environmentIris.  相似文献   

4.
5.
We present an algorithm that predicts musical genre and artist from an audio waveform. Our method uses the ensemble learner ADABOOST to select from a set of audio features that have been extracted from segmented audio and then aggregated. Our classifier proved to be the most effective method for genre classification at the recent MIREX 2005 international contests in music information extraction, and the second-best method for recognizing artists. This paper describes our method in detail, from feature extraction to song classification, and presents an evaluation of our method on three genre databases and two artist-recognition databases. Furthermore, we present evidence collected from a variety of popular features and classifiers that the technique of classifying features aggregated over segments of audio is better than classifying either entire songs or individual short-timescale features. Editor: Gerhard Widmer  相似文献   

6.
In this work we present Zeus, a distributed timed model checker that evolves from the TCTL model checker Kronos [13] and that currently can handle backwards computation of reachability properties [2] over timed automata [3].Zeus was developed following a software architecture-centric approach. Its conceptual architecture was conceived to be sufficiently modular to house several features such as a priori graph partitioning, synchronous and asynchronous computation, communication piggybacking, delayed messaging, and dead-time utilization.Surprisingly enough, early experiments pinpointed the difficulties of getting speedups using asynchronous versions and showed interesting results on the synchronous counterpart, although being intuitively less attractive.  相似文献   

7.
8.
Two base algorithms are known for reachability verification over timed automata. They are called forward and backwards, and traverse the automata edges using either successors or predecessors. Both usually work with a data structure called Difference Bound Matrices (DBMs). Although forward is better suited for on-the-fly construction of the model, the one known as backwards provides the basis for the verification of arbitrary formulae of the TCTL logic, and more importantly, for controller synthesis. Zeus is a distributed model checker for timed automata that uses the backwards algorithm. It works assigning each automata location to only one processor. This design choice seems the only reasonable way to deal with some complex operations involving many DBMs in order to avoid huge overheads due to distribution. This article explores the limitations of Zeus-like approaches for the distribution of timed model checkers.Our findings justify why close-to-linear speedups are so difficult –and sometimes impossible– to achieve in the general case. Nevertheless, we present mechanisms based on the way model checking is usually applied. Among others, these include model-topology-aware partitioning and on-the-fly workload redistribution. Combined, they have a positive impact on the speedups obtained.
F. SchapachnikEmail:
  相似文献   

9.
Various approaches to the problem of programming recursively defined functions infortran are discussed. The only acceptable method in ASAfortran is shown to be most easily programmed using a stack containing not addresses, but function arguments. The stack is built up and, when full, the function is constructed from the stack elements. A sequence of examples of increasing complexity is given to demonstrate the technique, including one in which a queue is found to be more appropriate than a stack. The emphasis throughout is on the simplicity of the technique.  相似文献   

10.
Much work has been done to clarify the notion of metamodelling and new ideas, such as strict metamodelling, distinction between ontological and linguistic instantiation, unified modelling elements and deep instantiation, have been introduced. However, many of these ideas have not yet been fully developed and integrated into modelling languages with (concrete) syntax, rigorous semantics and tool support. Consequently, applying these ideas in practice and reasoning about their meaning is difficult, if not impossible. In this paper, we strive to add semantic rigour and conceptual clarity to metamodelling through the introduction of Nivel, a novel metamodelling language capable of expressing models spanning an arbitrary number of levels. Nivel is based on a core set of conceptual modelling concepts: class, generalisation, instantiation, attribute, value and association. Nivel adheres to a form of strict metamodelling and supports deep instantiation of classes, associations and attributes. A formal semantics is given for Nivel by translation to weight constraint rule language (WCRL), which enables decidable, automated reasoning about Nivel. The modelling facilities of Nivel and the utility of the formalisation are demonstrated in a case study on feature modelling.
Timo AsikainenEmail:
  相似文献   

11.
This paper describes how a computer-algebra system can solve variational optimization problems analytically. For a calculus-of-variations problem, users provide functional integrands and constraints. A program derives corresponding Euler-Lagrange equations, together perhaps with first integrals. Other programs attempt analytic solution of these equations. For an optimal control problem, users provide analytic expressions for the differential constraints on the state variables. A program determines the corresponding Hamiltonian and differential equations for the auxiliary variables, together with solutions to any trivial auxiliary equations. Other programs attempt analytic solution of the remaining equations while maximizing the Hamiltonian.This material is based upon work supported by the National Science Foundation under Grant No. MCS75-22983 A01.  相似文献   

12.
Over the past few years researchers have been investigating the enhancement of visual tracking performance by devising trackers that simultaneously make use of several different features. In this paper we investigate the combination of synchronous visual trackers that use different features while treating the trackers as “black boxes”. That is, instead of fusing the usage of the different types of data as has been performed in previous work, the combination here is allowed to use only the trackers' output estimates, which may be modified before their propagation to the next time step. We propose a probabilistic framework for combining multiple synchronous trackers, where each separate tracker outputs a probability density function of the tracked state, sequentially for each image. The trackers may output either an explicit probability density function, or a sample-set of it via Condensation. Unlike previous tracker combinations, the proposed framework is fairly general and allows the combination of any set of trackers of this kind, even in different state-spaces of different dimensionality, under a few reasonable assumptions. The combination may consist of different trackers that track a common object, as well as trackers that track separate, albeit related objects, thus improving the tracking performance of each object. The benefits of merely using the final estimates of the separate trackers in the combination are twofold. Firstly, the framework for the combination is fairly general and may be easily used from the software aspects. Secondly, the combination may be performed in a distributed setting, where each separate tracker runs on a different site and uses different data, while avoiding the need to share the data. The suggested framework was successfully tested using various state-spaces and datasets, demonstrating that fusing the trackers' final distribution estimates may indeed be applicable. Electronic supplementary material Electronic supplementary material is available for this article at and accessible for authorised users. First online version published in October, 2005  相似文献   

13.
System specification with Lotos (Language Of Temporal Ordering Specification) is briefly introduced. To make test generation practicable, specifications are annotated with event constraints using PCL (Parameter Constraint Language) as a means of stating test purposes. Automated test generation can then use the principle of input-output conformance to check whether an implementation agrees with its specification. Test suites are generated by a transition tour that either visits every transition at least once (for infinite behaviour) or follows every path (for finite behaviour). The approach is applied to a case study in which tests are generated for radiotherapy accelerators used in cancer treatment. A typical specification and set of test purposes yields 256 test cases that can be executed manually or automatically. The goal is to determine situations in which an accelerator does not behave in conformity with its specification.  相似文献   

14.
The U.S. Air Force (USAF) created the Software Technology Support Center (STSC) at Hill AFB, Utah to enable Air Force software engineering organizations to identify, evaluate, and adopt technologies that will improve their software production. As part of this mission, the STSC collects detailed information about software tools and solicits frank assessments from tool users. Then, as a free service, the STSC provides a customized tools list to anyone within the United States, based on a user's requirements (e.g. hardware platform, operating system, etc.). This article will discuss the STSC's functional goal to act as a central repository of software information with an emphasis on the software reengineering technology domain.  相似文献   

15.
We describe two algorithms, BiBoost (Bipartite Boosting) and MultBoost (Multiparty Boosting), that allow two or more participants to construct a boosting classifier without explicitly sharing their data sets. We analyze both the computational and the security aspects of the algorithms. The algorithms inherit the excellent generalization performance of AdaBoost. Experiments indicate that the algorithms are better than AdaBoost executed separately by the participants, and that, independently of the number of participants, they perform close to AdaBoost executed using the entire data set. Responsible Editor: Charu Aggarwal.  相似文献   

16.
A new technique for automatic clustering of multivariate data is proposed. In this approach a performance index for determining optimal clusters is introduced. This performance index is expressed in terms of the ratio of the minimum interset distance to maximum intraset distance. The optimal clusters are found when the performance index reaches a global maximum. If there are alternative groupings with equal number of clusters, the one with the largest performance index is chosen.  相似文献   

17.
We compare four tools regarding their suitability for teaching formal software verification, namely the Frege Program Prover, the Key system, Perfect Developer, and the Prototype Verification System (PVS). We evaluate them on a suite of small programs, which are typical of courses dealing with Hoare-style verification, weakest preconditions, or dynamic logic. Finally we report our experiences with using Perfect Developer in class.  相似文献   

18.
Schedulability analysis of global edf   总被引:1,自引:1,他引:0  
The multiprocessor edf scheduling of sporadic task systems is studied. A new sufficient schedulability test is presented and proved correct. It is shown that this test generalizes the previously-known exact uniprocessor edf-schedulability test, and that it offers non-trivial quantitative guarantees (including a resource augmentation bound) on multiprocessors.
Sanjoy BaruahEmail:
  相似文献   

19.
This paper presented a simple PROLOG implementation for Arrow’s Social welfare function (SWF). Arrow (Social choice and individual values, Yale University Press, 1963) proved that any SWF which satisfies a set of conditions IIA, Pareto, and unrestricted domain should be dictatorial. The PROLOG program can prove the theorem for 3-alternative 2-agent case. With a minor modification it proves a version of the theorem without the Pareto condition by Wilson (Journal of Economic Theory, 5, 478–486, 1972).  相似文献   

20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号