Author name cluster

Menachem Magidor

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

I&C Journal 1996 Journal Article

A Temporal Logic for Proving Properties of Topologically General Executions

Rachel Ben-Eliyahu
Menachem Magidor

We present a generalization of the temporal propositional logic of linear time which is useful for stating and proving properties of the generic execution sequence of a parallel program or a non-deterministic program. The formal system we present is exactly that same as the third of three logics presented by Lehmann and Shelah (Information and Control 53, 165–198 (1982)), but we give it a different semantics. The models are tree models of arbitrary size similar to those used in branching time temporal logic. The formulation we use allows us to state properties of the “co-meagre” family of paths, where the term “co-meagre” refers to a set whose complement is of the first category in Baire's classification looking at the set of paths in the model as a metric space. Our system is decidable, sound, and, complete for models of arbitrary size, but it has the finite model property; namely, every sentence having a model has a finite model.

Details DOI

TARK Conference 1996 Conference Paper

Distance Semantics for Belief Revision

Karl Schlechta
Daniel Lehmann 0001
Menachem Magidor

A vast and interesting family of natural semantics for Belief Revision is defined. Suppose one is given a distance d between any two models. One may define the revision of a theory K by a formula a as the theory defined by the set of all those models of a that are closest, by d, to the set of models of K. This family is characterized by a set of rationality postulates that extends the AGM postulates. The new postulates describe properties of iterated revisions.

Details

TCS Journal 1994 Journal Article

On the mutual-exclusion problem — a quest for minimal solutions

Uri Abraham
Menachem Magidor

Abraham, U. and M. Magidor, On the mutual-exclusion problem — a quest for minimal solutions, Theoretical Computer Science 129 (1994) 1–38. We investigate here the question of finding the minimal requirements for the registers used by n processes that solve the critical-section problem. For two processes, we show that there cannot be a solution to the critical-section problem if the two registers used are regular and of size 2 and 3. For n processes, this result generalizes to show the impossibility of a solution with regular registers if the total size of the registers is 3n − 1. This is the best result for n = 2 since there are solution (presented here) in which regular registers of total size 6 are used. The impossibility proof depends on a careful analysis of infinite protocol automata, and therefore a detailed definition of such automata and their semantics is developed first.

Details DOI

AIJ Journal 1992 Journal Article

What does a conditional knowledge base entail?

Daniel Lehmann
Menachem Magidor

This paper presents a logical approach to nonmonotonic reasoning based on the notion of a nonmonotonic consequence relation. A conditional knowledge base, consisting of a set of conditional assertions of the type if … then …, represents the explicit defeasible knowledge an agent has about the way the world generally behaves. We look for a plausible definition of the set of all conditional assertions entailed by a conditional knowledge base. In a previous paper, Kraus and the authors defined and studied preferential consequence relations. They noticed that not all preferential relations could be considered as reasonable inference procedures. This paper studies a more restricted class of consequence relations, rational relations. It is argued that any reasonable nonmonotonic inference procedure should define a rational relation. It is shown that the rational relations are exactly those that may be represented by a ranked preferential model, or by a (nonstandard) probabilistic model. The rational closure of a conditional knowledge base is defined and shown to provide an attractive answer to the question of the title. Global properties of this closure operation are proved: it is a cumulative operation. It is also computationally tractable. This paper assumes the underlying language is propositional.

Details DOI

AIJ Journal 1990 Journal Article

Nonmonotonic reasoning, preferential models and cumulative logics

Sarit Kraus
Daniel Lehmann
Menachem Magidor

Many systems that exhibit nonmonotonic behavior have been described and studied already in the literature. The general notion of nonmonotonic reasoning, though, has almost always been described only negatively, by the property it does not enjoy, i. e. monotonicity. We study here general patterns of nonmonotonic reasoning and try to isolate properties that could help us map the field of nonmonotonic reasoning by reference to positive properties. We concentrate on a number of families of nonmonotonic consequence relations, defined in the style of Gentzen [13]. Both proof-theoretic and semantic points of view are developed in parallel. The former point of view was pioneered by Gabbay [10], while the latter has been advocated by Shoham [38]. Five such families are defined and characterized by representation theorems, relating the two points of view. One of the families of interest, that of preferential relations, turns out to have been studied by Adams [2]. The preferential models proposed here are a much stronger tool than Adams' probabilistic semantics. The basic language used in this paper is that of propositional logic. The extension of our results to first-order predicate calculi and the study of the computational complexity of the decision problems described in this paper will be treated in another paper.

Details DOI

TARK Conference 1990 Conference Paper

Preferential Logics: the Predicate Calculus Case

Daniel Lehmann 0001
Menachem Magidor

Suppose a knowledge base contains information on how the world generally behaves and in particular contains the information that birds, normally fly. Suppose that we obtain the information that Tweety is a bird, why should we conclude that it is plausible that Tweety flies? The answer to this question is unexpectedly sophisticated since the obvious substitution rule has to be rejected. Our answer to this question is based on an extension to predicate calculus of the ideas presented in [7]. Preferential consequence relations over predicate calculi are defined. In addition to the rules satisfied by those relations in the propositional case, they satisfy two rules dealing with quantifiers. These rules are not enough to enable us to conclude that Tweety flies. The rational closure construction defined in [7] should be generalized to the predicate calculus case and, in the rational closure, Tweety should fly.

Details