Author name cluster

Daniel Lehmann

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.

7 papers

1 author row

FLAP Journal 2024 Journal Article

Projection-algebras and Quantum Logic

Daniel Lehmann

P-algebras are a non-commutative, non-associative generalization of Boolean algebras that are for quantum logic what Boolean algebras are for classical logic. P-algebras have type ⟨X, 0, ′, ·⟩ where 0 is a constant, ′ is unary and · is binary. Elements of X are called features. A partial order is defined on the set X of features by x ≤ y iff x · y = x. Features commute, i. e. , x · y = y · x iff x · y ≤ x. Features x and y are said to be orthogonal iff x · y = 0 and orthogonality is a symmetric relation. The operation + is defined as the dual of · and it is com- mutative on orthogonal features. The closed subspaces of a separable Hilbert space form a P-algebra under orthogonal complementation and projection of a subspace onto another one. P-algebras are complemented orthomodular posets but they are not lattices. Existence of least upper bounds for ascending se- quences is equivalent to the existence of least upper bounds for countable sets of pairwise orthogonal elements. Atomic algebras are defined and their main properties are studied. The logic of P-algebras is then completely characterized. The language contains a unary connective corresponding to the operation ′ and a binary connective corresponding to the operation “·”. It is a substructural logic of sequents where the Exchange rule is extremely limited. It is proved to be sound and complete for P-algebras.

PDF Details

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 1991 Journal Article

Rationality, transitivity, and contraposition

Michael Freund
Daniel Lehmann
Paul Morris

The purpose of this note is to compare the rule of Rational Monotonicity proposed in [3] and different rules expressing some weak forms of Transitivity and Contraposition. We present four weak forms of Transitivity that, in preferential logic, are equivalent to Rational Monotonicity and a weak form of Contraposition that is strictly weaker than Rational Monotonicity but equivalent to it in the presence of Disjunctive Rationality.

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

TCS Journal 1988 Journal Article

Knowledge, belief and time

Sarit Kraus
Daniel Lehmann

In the conclusion of [7] Halpern and Moses expressed their interest in a logical system in which one could talk about knowledge and belief (and belief about knowledge, knowledge about belief and so on). We investigate such systems. In the first part of the paper knowledge and belief, without time, are considered. Common knowledge and common belief are defined and compared. A logical system and a family of models are proposed, a completeness result is proved and a decision procedure described. In the second part of the paper, time is considered. Different notions of beliefs are distinguished, obeying different properties of persistence. One interpretation of belief which obeys a very strong persistence axiom is put forward and used in the analysis of the “wise men” puzzle.

Details DOI

TCS Journal 1984 Journal Article

Symmetric and economical solutions to the mutual exclusion problem in a distributed system

Shimon Cohen
Daniel Lehmann
Amir Pnueli

The mutual exclusion problem in a distributed system, in which each process has a memory of its own, into which it has exclusive write privileges but from which others may read, is reconsidered. Symmetric solutions are looked for. It is shown that, though no such solution may be deterministic, there are probabilistic solutions. Different solutions are provided for two processes, and then a solution is proposed for any number of processes. The solutions offered are amenable to a formal proof of their correctness with a small effort. The solutions are correct even against a very well informed scheduler, unlike Rabin's probabilistic solution to the mutual exclusion problem in a centralized system. Some of the solutions are correct even against an evil scheduler the knows in advance the results of the future random draws, in sharp contrast with the algorithms of Lehmann and Rabin (1981). The solutions are economical: mutual exclusion between two processes may be achieved with variables capable of holding four different values (to be compared with Peterson and Fischer's three), mutual exclusion between n processes may be achieved with variables capable of holding ten different values (to be compared with Peterson and Fischer's fourteen). All solutions have been attained by careful reasoning and not by an exhaustive computer search: they exhibit general principles of design that may be useful in solving other similar problems.

Details DOI

TCS Journal 1982 Journal Article

Epis need not be dense

Daniel Lehmann
Ana Pasztor

In [6] and [7] Meseguer conjectured that in the category Pos(ω) of ω-complete posets and ω-continuous maps the epis are exactly the dense maps. This paper exhibits a counter-example to Meseguer's conjecutre, draws a number of negative conclusions and strengthens another of Meseguer's results. By embedding Pos(ω) in the category of partial algebras of an adequate type, a better understanding is obtained both of these results and of the conjecture.

Details DOI