We study strategy improvement algorithms for mean-payoff and parity games. We describe a structural property of these games, and we show that these structures can affect the behaviour of strategy improvement. We show ...
详细信息
ISBN:
(纸本)9783642175107
We study strategy improvement algorithms for mean-payoff and parity games. We describe a structural property of these games, and we show that these structures can affect the behaviour of strategy improvement. We show how awareness of these structures can be used to accelerate strategy improvement algorithms. We call our algorithms non-oblivious because they remember properties of the game that they have discovered in previous iterations. We show that non-oblivious strategy improvement algorithms perform well on examples that are known to be hard for oblivious strategy improvement. Hence, we argue that previous strategy improvement algorithms fail because they ignore the structural properties of the game that they are solving.
As the abundance of web services on the World Wide Web increase, designing effective approaches for web service selection and recommendation has become more and more important. In this paper we focus on an approach dy...
详细信息
ISBN:
(纸本)9780769541549
As the abundance of web services on the World Wide Web increase, designing effective approaches for web service selection and recommendation has become more and more important. In this paper we focus on an approach dynamically offering services that fit the end-users' interests. To this end, we present a hybrid approach, coupling pure and classic collaborative-filtering methods and a semantic content-based method. On the one hand the former methods are used to automatically recommend services depending on other similar users, based on profiles, preferences and historical experience. On the other hand our semantic content-based approach performs Description logic based reasoning on semantic descriptions of services, in order to analysis semantic similarity of services. this approach further restricts the potential results and then ensuring a semantic recommendation of services. Finally we discuss its advantages and weaknesses.
logic-based Benders decomposition can combine mixed integer programming and constraint programming to solve planning and scheduling problems much faster than either method alone. We find that a similar technique can b...
详细信息
ISBN:
(纸本)9783642135194
logic-based Benders decomposition can combine mixed integer programming and constraint programming to solve planning and scheduling problems much faster than either method alone. We find that a similar technique can be beneficial for solving pure scheduling problems as the problem size scales up. We solve single-facility non-preemptive scheduling problems with time windows and long time horizons that are divided into segments separated by shutdown times (such as weekends). the objective is to find feasible solutions, minimize makespan, or minimize total tardiness.
this article presents a technique for Stream reasoning, consisting in incremental maintenance of materializations of ontological entailments in the presence of streaming information. Previous work, delivered in the co...
详细信息
ISBN:
(纸本)9783642134852
this article presents a technique for Stream reasoning, consisting in incremental maintenance of materializations of ontological entailments in the presence of streaming information. Previous work, delivered in the context of deductive databases, describes the use of logicprogramming for the incremental maintenance of such entailments. Our contribution is a new technique that exploits the nature of streaming data in order to efficiently maintain materialized views or RDF triples, which can be used by a reasoner. By adding expiration time information to each RDF triple, we show that;it is possible to compute a new complete and correct materialization whenever a new window of streaming data. arrives, by dropping explicit statements and entailments that are no longer valid, and then computing when the RDF triples inserted within the window will expire. We Provide experimental evidence that our approach significantly reduces the time required to compute a new materialization at each window change, and opens up for several further optimizations.
Because of their self-x properties Organic Computing systems are hard to verify. Nevertheless in safety critical domains one may want to give behavioral guarantees. One technique to reduce complexity of the overall ve...
详细信息
ISBN:
(纸本)9783642165757
Because of their self-x properties Organic Computing systems are hard to verify. Nevertheless in safety critical domains one may want to give behavioral guarantees. One technique to reduce complexity of the overall verification task is applying composition theorem. In this paper we present a technique for formal specification and compositional verification of Organic Computing systems. Separation of self-x and functional behavior has amongst others, advantages for the formal specification. We present how the specification of self-x behavior can be integrated into an approach for compositional verification of concurrent systems, based on Interval Temporal logic. the presented approach has full tool support withthe KIV interactive theorem prover.
Trust is, in some cases, being considered as a requirement in highly distributed communication scenarios. Before accessing a particular service, a trust model is then being used in these scenarios to determine if the ...
详细信息
Jerabek showed in 2008 that cuts in propositional-logic deep-inference proofs can be eliminated in quasipolynomial time. the proof is an indirect one relying on a result of Atserias, Galesi and Pudlak about monotone s...
详细信息
ISBN:
(纸本)9783642175107
Jerabek showed in 2008 that cuts in propositional-logic deep-inference proofs can be eliminated in quasipolynomial time. the proof is an indirect one relying on a result of Atserias, Galesi and Pudlak about monotone sequent calculus and a correspondence between this system and cut-free deep-inference proofs. In this paper we give a direct proof of Jerabek's result: we give a quasipolynomial-time cut-elimination procedure in propositional-logic deep inference. the main new ingredient is the use of a computational trace of deep-inference proofs called atomic flows, which are both very simple (they trace only structural rules and forget logical rules) and strong enough to faithfully represent the cut-elimination procedure.
Coalgebraic description logics offer a common semantic umbrella for extensions of description logics withreasoning principles outside relational semantics, e.g. quantitative uncertainty, non-monotonic conditionals, o...
详细信息
ISBN:
(纸本)9783642142024
Coalgebraic description logics offer a common semantic umbrella for extensions of description logics withreasoning principles outside relational semantics, e.g. quantitative uncertainty, non-monotonic conditionals, or coalitional power. Specifically, we work in coalgebraic logic with global assumptions (i.e. a general TBox), nominals, and satisfaction operators, and prove soundness and completeness of an associated tableau algorithm of optimal complexity EXPTIME. the algorithm uses the (known) tableau rules for the underlying modal logics, and is based on on global caching, which raises hopes of practically feasible implementation. Instantiation of this result to concrete logics yields new algorithms in all cases including standard relational hybrid logic.
the proceedings contain 15 papers. the topics discussed include: the refinement of choreographed multi-agent systems;goal generation from possibilistic beliefs based on trust and distrust;monitoring directed obligatio...
ISBN:
(纸本)3642113540
the proceedings contain 15 papers. the topics discussed include: the refinement of choreographed multi-agent systems;goal generation from possibilistic beliefs based on trust and distrust;monitoring directed obligations with flexible deadlines: a rule-based approach;unifying the intentional and institutional semantics of speech acts;tableaux for acceptance logic;ontology and time evolution of obligations and prohibitions using semantic web technology;prioritized goals and subgoals in a logical account of goal change - a preliminary report;declarative and numerical analysis of edge creation process in trust-based social networks;computing utility from weighted description logic preference formulas;explaining and predicting the behavior of BDI-based agents in role-playing games;correctness properties for multiagent systems;and reasoning and planning with cooperative actions for multiagents using answer set programming.
In this paper we present loose programming, an approach designed to enable process developers to design their application-specific processes in an intuitive style. Key to this approach is the concept of loose specific...
详细信息
ISBN:
(纸本)9780769542416
In this paper we present loose programming, an approach designed to enable process developers to design their application-specific processes in an intuitive style. Key to this approach is the concept of loose specification, a graphical formalism that allows developers to express their processes just by sketching them as kinds of flow graphs without caring about types, precise knowledge about the available process components or the availability of resources. they only have to specify the rough process flow graphically in terms of ontologically defined 'semantic' entities. these loose specifications are then concretized to fully executable process code automatically by means of a combination of 1) data-flow analysis, ensuring the availability of the required resources, 2) temporal logic-based process synthesis, resolving type conflicts and taking care of correct component instantiation, and 3) model checking, to ensure global intents and invariants expressed in temporal logic.
暂无评论