We define two-dimensional rational automata for pictures as an extension of classical finite automata for strings. they are obtained replacing the finite relation computed by the transition function with a rational re...
详细信息
ISBN:
(纸本)9783642358432
We define two-dimensional rational automata for pictures as an extension of classical finite automata for strings. they are obtained replacing the finite relation computed by the transition function with a rational relation computed by a transducer. the model provides a uniform setting for the most important notions, techniques and results presented in the last decades for recognizable two-dimensional languages, and establishes new connections between one- and two-dimensional language theory.
Many recent applications of interest involve self-interested participants. As such participants, termed agents, may manipulate the algorithm for their own benefit, a new challenge emerges: the design of algorithms and...
详细信息
ISBN:
(纸本)3540413480
Many recent applications of interest involve self-interested participants. As such participants, termed agents, may manipulate the algorithm for their own benefit, a new challenge emerges: the design of algorithms and protocols that perform well when the agents behave according to their own self-interest. this led several researchers to consider computational models that are based on a sub-field of game-theory and micro-economics called mechanism design. this paper introduces this topic mainly through examples. It demonstrates that in many cases selfishness can be satisfactorily overcome, surveys some of the recent trends in this area and presents new challenging problems. the paper is mostly based on classic results from mechanism design as well as on recent work by the author and others.
the proceedings contain 30 papers. the topics discussed include: applications of answer set programming where theory meets practice;when is it morally acceptable to break the rules? a preference-based approach;formal ...
the proceedings contain 30 papers. the topics discussed include: applications of answer set programming where theory meets practice;when is it morally acceptable to break the rules? a preference-based approach;formal reasoning methods for explainability in machine learning;from probabilistic logics to neuro-symbolic artificial intelligence;norms, policy and laws: modeling, compliance and violation;datalog-based systems can use incremental SMT solving;formal semantics and scalability for datalog with aggregates: a cardinality-based solution;a logic programming approach to regression based repair of incorrect initial belief states;and a hybrid neuro-symbolic approach for complex event processing.
computer game-playing is a challenging topic in artificial intelligence. the recent results by the computer programs DEEP BLUE (1996, 1997) and DEEP JUNIOR (2002) against Kasparov show the power of current game-tree s...
详细信息
ISBN:
(纸本)3540207791
computer game-playing is a challenging topic in artificial intelligence. the recent results by the computer programs DEEP BLUE (1996, 1997) and DEEP JUNIOR (2002) against Kasparov show the power of current game-tree search algorithms in Chess. this success is owed to the fruitful combination of the theoretical development of algorithms and their practical application. As an example of the theoretical development we discuss a game-tree algorithm called Opponent-Model search. In contrast to most current algorithms, this algorithm uses an opponent model to predict the opponent's moves and uses these predictions to lure the opponent into uncomfortable positions. We concentrate on the time complexity of two different implementations of the algorithm and show how these are derived. Moreover, we discuss some possible dangers when applying Opponent-Model search in practice.
We present a characterization of the class of context-free trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed b...
详细信息
ISBN:
(纸本)9783642183805
We present a characterization of the class of context-free trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed by an external pushdown store.
the problem of finding k minimum energy, edge-disjoint paths in wireless networks (MEEP) arises in the context of routing and belongs to the class of range assignment problems. A polynomial algorithm which guarantees ...
详细信息
ISBN:
(纸本)9783540695066
the problem of finding k minimum energy, edge-disjoint paths in wireless networks (MEEP) arises in the context of routing and belongs to the class of range assignment problems. A polynomial algorithm which guarantees a factor-k-approximation for this problem has been presented before, but its complexity status was open. In this paper we prove that MEEP is NP-hard and give new lower and upper bounds on the approximation factor of the k-approximation algorithm. For MEEP on acyclic graphs we introduce an exact, polynomial algorithm which is then extended to a heuristic for arbitrary graphs.
Games are a classical model in the synthesis of controllers in the open setting. In particular, games of infinite length can represent systems which are not expected to reach a correct state, but rather to handle a co...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
Games are a classical model in the synthesis of controllers in the open setting. In particular, games of infinite length can represent systems which are not expected to reach a correct state, but rather to handle a continuous stream of events. Yet, even longer sequences of events have to be considered when infinite sequences of events can occur in finite time - Zeno behaviours. In this paper, we extend two-player games to this setting by considering plays of ordinal length. Our two main results are determinacy of reachability games of length less than w(w) on finite arenas, and the PSPACE-completeness of deciding the winner in such a game.
the Target Set Selection problem takes as an input a graph G and a non-negative integer threshold thr(v) for every vertex v. A vertex v can get active as soon as at least thr(v) of its neighbors have been activated. T...
详细信息
ISBN:
(纸本)9783319731179;9783319731162
the Target Set Selection problem takes as an input a graph G and a non-negative integer threshold thr(v) for every vertex v. A vertex v can get active as soon as at least thr(v) of its neighbors have been activated. the objective is to select a smallest possible initial set of vertices, the target set, whose activation eventually leads to the activation of all vertices in the graph. We show that Target Set Selection is in FPT when parameterized withthe combined parameters clique-width of the graph and the maximum threshold value. this generalizes all previous FPT-membership results for the parameterization by maximum threshold, and thereby solves an open question from the literature. We stress that the time complexity of our algorithm is surprisingly well-behaved and grows only single-exponentially in the parameters.
Motivated by a potentially flawed deployment of the. one time pad in a:recent quantum cryptographic application securing a bank transfer [1], we show how to implement a statistically secure system for message passing,...
详细信息
ISBN:
(纸本)354024302X
Motivated by a potentially flawed deployment of the. one time pad in a:recent quantum cryptographic application securing a bank transfer [1], we show how to implement a statistically secure system for message passing, that is, a channel with negligible failure rate secure against unbounded adversaries, using a one time pad based cryptosystem. We prove the security of our system in the framework put forward by Backes, Pfitzmann, and Waidner [2].
暂无评论