1,721,021 research outputs found
Module checking of strategic ability
No full textModule checking is a decision problem proposed in late 1990s to formalize verification of open systems, i.e., systems that must adapt their behavior to the input they receive from the environment. It was recently shown that module checking offers a distinctly different perspective from the better-known problem of model checking. So far, specifications in temporal logic CTL have been used for module checking. In this paper, we extend module checking to handle specifications in alternating-time temporal logic (ATL). We define the semantics of ATL module checking, and show that its expressivity strictly extends that of CTL module checking, as well as that of ATL itself. At the same time, we show that ATL module checking enjoys the same computational complexity as CTL module checking. We also investigate a variant of ATL module checking where the environment acts under uncertainty. Finally, we revisit the semantics of ability in the module checking problem, and propose a variant where strategies of agents in the module depend only on what the agents are able to observe
Module checking for uncertain agents
Get PDFModule checking is a decision problem proposed in late 1990s to formalize verification of open systems, i.e., systems thatmust adapt their behavior to the input they receive from the environment. It was recently shown that module checking offers a distinctly different perspective from the better-known problem of model checking. Module checking has been studied in several variants. Syntactically, specifications in temporal logic CTL and strategic logic ATL have been used. Semantically, the environment was assumed to have either perfect or imperfect information about the global state of the interaction. In this work, we rectify our approach to imperfect information module checking from the previous paper. Moreover, we study the variant of module checking where also the system acts under uncertainty. More precisely, we assume that the system consists of one or more agents whose decision making is constrained by their observational capabilities. We propose an automata-based verification procedure for the new problem, and establish its computational complexit
On module checking and strategies
No full textTwo decision problems are very close in spirit: module checking of CTL/CTL* and model checking of ATL/ATL*. The latter appears to be a natural multi-agent extension of the former, and it is commonly believed that model checking of ATL(*) subsumes module checking of CTL(*) in a straightforward way. Perhaps because of that, the exact relationship between the two has never been formally established.
A more careful look at the known complexity results, however, makes one realize that the relationship is somewhat suspicious. In particular, module checking of CTL is Exptime-complete, while model checking of ATL is only time-complete. Thus, the (seemingly) less expressive framework yields significantly higher computational complexity than the (seemingly) more expressive one. This suggests that the relationship may not be as simple as believed. In this paper, we show that the difference is indeed fundamental. The way in which behavior of the environment is understood in module checking cannot be equivalently characterized in ATL(*). Conversely, if one wants to embed module checking in ATL(*) then its semantics must be extended with two essential features, namely nondeterministic strategies and long-term commitment to strategies
Model Checking Strategic Ability - Why, What, and Especially: How? (Invited Paper)
No full textAutomated verification of discrete-state systems has been a hot topic in computer science for over 35 years. Model checking of temporal and strategic properties is one of the most prominent and most successful approaches here. In this talk, I present a brief introduction to the topic, and mention some relevant properties that one might like to verify this way. Then, I describe some recent results on approximate model checking and model reductions, which can be applied to facilitate verification of notoriously hard cases
Extending Fuzzy Logics to Support Decisions
No full text. In this paper a concept of evaluation schema for uncertain statements is proposed. The aim is to represent and process knowledge and to support decision making under uncertainty, involving the information with unmeasurable uncertainty in the reasoning process. This 'uncertainty logic' is based on fuzzy logics and L/ukasiewicz three-valued logic, but it's underlied by a richer structure that makes more subtle analysis of statements possible. The logic is a kind of L-fuzzy logic formally. However, its ontological motivations are different. Keywords: knowledge representation, reasoning under uncertainty, decision making, fuzzy logics, three-valued logic. 1 Motivations 1.1 Philosophical Motivations According to (Klir & Folger 1988), situations of uncertainty arise either in a world that's vague or in a world of imperfect information (ambiguity; uncertainty in the narrow sense). There are some approaches to the problem of representing and processing uncertain information; fuzzy measu..
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Knowledge and Strategic Ability for Model Checking: A Refined Approach
No full textWe present a translation that reduces epistemic operators to strategic operators in the context of model checking. The translation is a refinement of the one from [7, 9], and it improves on the previous scheme in two ways. First, it does not suffer any blowup in the length of formulae (the one from [7, 9] did). Second, the new translation is defined in a more general setting: additional constraints can be imposed on strategy profiles that agents can execute; we show that the translation is still valid in such a general case.
On the Relationship Between Playing Rationally and Knowing How to Play: A Logical Account
No full textVariations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
