ICS PAS Reports


"ICS PAS Reports" Archive (1995 - 2014) - link

2015 -

TitleAuthors Release dateLiczba stron Abstract:
1037. Static Large Games with Finitely Many Types of Players and StrategiesAndrzej WieczorekDecember 201618The 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 LogicPiotr Dembiński, Wojciech Jamroga, Antoni Mazurkiewicz, Wojciech PenczekDecember 201632
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 ActionJózef WinkowskiOctober 201632
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 typeStanisław AmbroszkiewiczOctober 201546
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 ActivitiesJózef WinkowskiOctober 201515
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 RecallWociech JamrogaSeptember 201517
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 DatabasesMaciej SzreterSeptember 201531
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

Print

ATTENTION! This site uses cookies and similar technologies.

If you do not change your browser settings, you automatically agree to this.

I understand