ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

1

Electronic Resource

Uncertainty, belief, and probability (1991)

FAGIN, RONALD ; HALPERN, JOSEPH Y.

Oxford, UK : Blackwell Publishing Ltd

Computational intelligence 7 (1991), S. 0

add to mindlist on the mindlist

Details

ISSN: 1467-8640

Source: Blackwell Publishing Journal Backfiles 1879-2005

Topics: Computer Science

Notes: We introduce a new probabilistic approach to dealing with uncertainty, based on the observation that probability theory does not require that every event be assigned a probability. For a nonmeasurable event (one to which we do not assign a probability), we can talk about only the inner measure and outer measure of the event. In addition to removing the requirement that every event be assigned a probability, our approach circumvents other criticisms of probability-based approaches to uncertainty. For example, the measure of belief in an event turns out to be represented by an interval (defined by the inner and outer measures), rather than by a single number. Further, this approach allows us to assign a belief (inner measure) to an event E without committing to a belief about its negation -E (since the inner measure of an event plus the inner measure of its negation is not necessarily one). Interestingly enough, inner measures induced by probability measures turn out to correspond in a precise sense to Dempster-Shafer belief functions. Hence, in addition to providing promising new conceptual tools for dealing with uncertainty, our approach shows that a key part of the important Dempster-Shafer theory of evidence is firmly rooted in classical probability theory.Cet article présente une nouvelle approche probabiliste en ce qui concerne le traitement de l'incertitude; celle-ci est basée sur l'observation que la théorie des probabilityés n'exige pas qu'une probabilityé soit assignée à chaque événement. Dans le cas d'un événement non mesurable (un événement pour lequel on n'assigne aucune probabilityé), nous ne pouvons discuter que de la mesure intérieure et de la mesure extérieure de l'évenément. En plus d'éliminer la nécessité d'assigner une probabilityéà l'événement, cette nouvelle approche apporte une réponse aux autres critiques des approches à l'incertitude basées sur des probabilityés. Par exemple, la mesure de croyance dans un événement est représentée par un intervalle (défini par la mesure intérieure et extérieure) plutǒt que par un nombre unique. De plus, cette approche nous permet d'assigner une croyance (mesure intérieure) à un événement E sans se compromettre vers une croyance à propos de sa négation -E (puisque la mesure intérieure d'un événement et la mesure intérieure de sa négation ne sont pas nécessairement une seule et unique mesure). II est intéressant de noter que les mesures intérieures qui résultent des mesures de probabilityé correspondent d'une manière précise aux fonctions de croyance de Dempster-Shafer. En plus de constituer un nouvel outil conceptuel prometteur dans le traitement de l'incertitude, cette approche démontre qu'une partie importante de la théorie de l'évidence de Dempster-Shafer est fermement ancrée dans la theorie classique des probabilityés.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1111/j.1467-8640.1991.tb00391.x

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

2

Electronic Resource

Reasoning about Knowledge: A Response by the Authors (1997)

Fagin, Ronald ; Halpern, Joseph Y. ; Moses, Yoram ; [et al.]

Springer

Minds and machines 7 (1997), S. 113-113

add to mindlist on the mindlist

Details

ISSN: 1572-8641

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Philosophy

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1023/A:1008278827378

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

3

Electronic Resource

Knowledge-based programs (1997)

Fagin, Ronald ; Halpern, Joseph Y. ; Moses, Yoram ; [et al.]

Springer

Distributed computing 10 (1997), S. 199-225

add to mindlist on the mindlist

Details

ISSN: 1432-0452

Keywords: Key words: Knowledge-based program ; Protocol ; Reasoning about knowledge ; multi-agent system

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science

Notes: Summary. Reasoning about activities in a distributed computer system at the level of the knowledge of individuals and groups allows us to abstract away from many concrete details of the system we are considering. In this paper, we make use of two notions introduced in our recent book to facilitate designing and reasoning about systems in terms of knowledge. The first notion is that of a knowledge-based program. A knowledge-based program is a syntactic object: a program with tests for knowledge. The second notion is that of a context, which captures the setting in which a program is to be executed. In a given context, a standard program (one without tests for knowledge) is represented by (i.e., corresponds in a precise sense to) a unique system. A knowledge-based program, on the other hand, may be represented by no system, one system, or many systems. In this paper, we provide a sufficient condition for a knowledge-based program to be represented in a unique way in a given context. This condition applies to many cases of interest, and covers many of the knowledge-based programs considered in the literature. We also completely characterize the complexity of determining whether a given knowledge-based program has a unique representation, or any representation at all, in a given finite-state context.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/s004460050038

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

4

Electronic Resource

Modelling knowledge and action in distributed systems (1989)

Halpern, Joseph Y. ; Fagin, Ronald

Springer

Distributed computing 3 (1989), S. 159-177

add to mindlist on the mindlist

Details

ISSN: 1432-0452

Keywords: Knowledge ; Action ; Standard protocol ; Knowledge-based protocol ; Run ; System ; Implementation

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science

Notes: Abstract We present a formal model that captures the subtle interaction between knowledge and action in distributed systems. We view a distributed system as a set ofruns, where a run is a function from time toglobal states and a global state is a tuple consisting of anenvironment state and alocal state for earch process in the system. This model is a generalization of those used in many previous papers.Actions in this model are associated with functions from global states to global states. Aprotocol is a function from local states to actions. We extend the standard notion of a protocol by definingknowledge-based protocols, ones in which a process' actions may depend explicitly on its knowledge. Knowledge-based protocols provide a natural way of describing how actions should take place in a distributed system. Finally, we show how the notion of one protocolimplementing another can be captured in our model.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01784885

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

5

Electronic Resource

The hierarchical approach to modeling knowledge and common knowledge (1999)

Fagin, Ronald ; Geanakoplos, John ; Halpern, Joseph Y. ; [et al.]

Springer

International journal of game theory 28 (1999), S. 331-365

add to mindlist on the mindlist

Details

ISSN: 1432-1270

Keywords: Key words: Common knowledge ; belief/knowledge hierarchies

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics , Economics

Notes: Abstract. One approach to representing knowledge or belief of agents, used by economists and computer scientists, involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs about the state of the world, his beliefs about other agents' beliefs about the world, his beliefs about other agents' beliefs about other agents' beliefs about the world, and so on. (Economists have typically modeled belief in terms of a probability distribution on the uncertainty space. In contrast, computer scientists have modeled belief in terms of a set of worlds, intuitively, the ones the agent considers possible.) We consider the question of when a countably infinite hierarchy completely describes the uncertainty of the agents. We provide various necessary and sufficient conditions for this property. It turns out that the probability-based approach can be viewed as satisfying one of these conditions, which explains why a countable hierarchy suffices in this case. These conditions also show that whether a countable hierarchy suffices may depend on the “richness” of the states in the underlying state space. We also consider the question of whether a countable hierarchy suffices for “interesting” sets of events, and show that the answer depends on the definition of “interesting”.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/s001820050114

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

6

Electronic Resource

Relaxing the Triangle Inequality in Pattern Matching (1998)

Fagin, Ronald ; Stockmeyer, Larry

Springer

International journal of computer vision 30 (1998), S. 219-231

add to mindlist on the mindlist

Details

ISSN: 1573-1405

Keywords: pattern matching ; shape matching ; triangle inequality ; distance measure ; image database

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science

Notes: Abstract Any notion of “closeness” in pattern matching should have the property that if A is close to B, and B is close to C, then A is close to C. Traditionally, this property is attained because of the triangle inequality (d(A, C) ≤ d(A, B) + d(B, C), where d represents a notion of distance). However, the full power of the triangle inequality is not needed for this property to hold. Instead, a “relaxed triangle inequality” suffices, of the form d(A, C) ≤ c(d(A, B) + d(B, C)), where c is a constant that is not too large. In this paper, we show that one of the measures used for distances between shapes in (an experimental version of) IBM's QBIC1 ("Query by Image Content") system (Niblack et al., 1993) satisfies a relaxed triangle inequality, although it does not satisfy the triangle inequality.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1023/A:1008023416823

Permalink