ICS PAS Reports
|Title||Authors||Release date||Liczba stron||Abstract:|
|1037. Static Large Games with Finitely Many Types of Players and Strategies||Andrzej Wieczorek||December 2016||18||The paper briefly presents a theory of games with finitely many infinite populations (types) each of whom has finitely many available strategies; the payoff of an individual player depends on the distribution of choices of strategies in all populations and his own particular choice. We give specific examples of applications of the theory in several areas: spatial allocation (of species), economic models – household economy and transportation networks. We also briefly discuss questions of computation of equilibria and relations of large games, as understood in the present paper, to ordinary matrix games, games with continuum of players and evolutionary game theory.|
Keywords: large game, equilibrium, strategy, type of player, spatial allocation, household economy, road traffic model, directed graph, Fibonacci numbers
|1036. Towards Partial Order Reductions for Fragments of Alternating-Time Temporal Logic||Piotr Dembiński, Wojciech Jamroga, Antoni Mazurkiewicz, Wojciech Penczek||December 2016||32|
A general semantics of strategic abilities of agents in asynchronous systems with and without perfect information is proposed, and some general complexity results for verification of strategic abilities in asynchronous systems are presented. A methodology for partial order reduction (POR) in verification of agents with imperfect information is developed, based on the notion of traces introduced by Mazurkiewicz. Two semantics of ATL*_x are considered and it is shown that for memoryless imperfect information (|=ir) contrary to memoryless perfect information (|=Ir), one can apply techniques known for LTL_x.
Keywords: Alternating-Time Temporal Logic, asynchronous systems, partial order reduction, traces
|1035. Towards a Universal Model of Action||Józef Winkowski||October 2016||32|
In the paper a model of action is described that is universal in the sense that it may serve to represent actions of any kind: discrete, continuous, or partially discrete and partially continuous. The model is founded on the assumption that an action is executed in a universe of objects. It describes how the possible executions change the situation of involved objects. It exploits the fact that executions are represented such that fragments of executions are represented such that their closed segments admit only trivial automorphisms. The model has an algebraic strucure and it is a directed complete partial order.
Keywords: Action, object, object instance, occurrence of object instance, execution, execution segment, execution fragment, execution structure, lposet, pomset, sequential composition, parallel composition, independent component, prefix order
|1035. Continuum as a primitive type||Stanisław Ambroszkiewicz||October 2015||46|
The paper is the revision, extended and full version of the short (6 pages) preliminary presentation of the grounding of the notion of Continuum given in Section 6 of the paper Types and operations ICS PAS Report No. 1030 (also at http://arxiv.org/abs/1501.03043). Here, primitive types (corresponding to the intuitive concept of Continuum) are introduced along with primitive operations, constructors, and relations. The paper is also at arXiv http://arxiv.org/abs/1510.02787
Keywords: Continuum, types, semantics, foundations of Mathematics
|1034. Partially Ordered Domains for Representing Activities||Józef Winkowski||October 2015||15|
The paper describes structures which can be used to represent activities of broad class. The concept of event structure is generalized to represent activities which may be discrete, continuous, or of mixed nature. Con_guration structures of the more general event structures are used to deńe axiomatically con_guration domains. Elements of such domains are abstract representants of runs of represented activities. The partial order of elements reects how each run extends to longer runs. It is shown that con_guration domains deńe event structures which can be interpreted as interactions of sets of objects.
Keywords: Activity, run, event, causal dependency relation, conict relation, event structure, con_guration, con_guration structure, partially ordered set, directed complete partially ordered set, con_guration domain, transition, region.
|1033. Underapproximating ATL with Imperfect Information and Imperfect Recall||Wociech Jamroga||September 2015||17|
We investigate the correspondence between model checking of af-AMCi and ATLir , on the example of reachability. We identify some of the reasons for the fact that these logics are of uncomparable expressivity. These observations form the basis for a novel method for underapproximating ATLir by means of fixed-point calculations. We introduce a special version of the next-step operator, called Persistent Imperfect Next-Step Operator h_iF and show how it can be used to define a new version of reachability that carries to ATLir.
Keywords: ATL, model checking, approximation
|1032. Bounded Abstract Planning in PlanICS based on Graph Databases||Maciej Szreter||September 2015||31|
The paper describes an application of a graph database to the abstract planning in the Planics composition system for web services. Abstract planning is the first stage of the service composition process, and consists in matching types of the services and objects processed by them, with some additional constraints. The result is an abstract plan matching the user query. The presented solution prunes the ontologies for the abstract planners, greatly improving efficiency and providing better scalability. This is of particular importance in the domain of web service composition, because usually systems are expected to produce answers immediatly.
Keywords: automatic composition of web services, graph databases, abstract planning