Review of Joseph Y. Halpern (ed.), Theoretical Aspects of Reasoning About Knowledge: Proceedings of the 1986 Conference (Los Altos, CA: Morgan Kaufmann, 1986),.

Vardi, M.Y., Verification of concurrent programs: the automata-theoretic framework, Annals of Pure and Applied Logic 51 79–98. We present an automata-theoretic framework to the verification of concurrent and nondeterministic programs. The basic idea is that to verify that a program P is correct one writes a program A that receives the computation of P as input and diverges only on incorrect computations of P. Now P is correct if and only if a program PA, obtained by combining P and (...) A, terminates. We formalize this idea in a framework of ω-automata with a recursive set of states. This unifies previous works on verification of fair termination and verification of temporal properties. (shrink)

What is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature; validity inference $(\sigma \vdash_\mathrm{v} \varphi$ if for every substitution $\tau$, the validity of $\tau \lbrack\sigma\rbrack$ entails the validity of $\tau\lbrack\varphi\rbrack)$, and truth inference $(\sigma \vdash_\mathrm{t} \varphi$ if for every substitution $\tau$, the truth of $\tau\lbrack\sigma\rbrack$ entails the truth of $\tau\lbrack\varphi\rbrack)$. In this paper we introduce a general semantic framework that allows us to investigate the notion of inference (...) more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic. (shrink)

In program synthesis, we transform a specification into a system that is guaranteed to satisfy the specification. When the system is open, then at each moment it reads input signals and writes output signals, which depend on the input signals and the history of the computation so far. The specification considers all possible input sequences. Thus, if the specification is linear, it should hold in every computation generated by the interaction, and if the specification is branching, it should hold in (...) the tree that embodies all possible input sequences. Often, the system cannot read all the input signals generated by its environment. For example, in a distributed setting, it might be that each process can read input signals of only part of the underlying processes. Then, we should transform a specification into a system whose output depends only on the readable parts of the input signals and the history of the computation. This is called synthesis with incomplete information. In this work we solve the problem of synthesis with incomplete information in its full generality. We consider linear and branching settings with complete and incomplete information. We claim that alternation is a suitable and helpful mechanism for coping with incomplete information. Using alternating tree automata, we show that incomplete information does not make the synthesis problem more complex, in both the linear and the branching paradigm. In particular, we prove that independently of the presence of incomplete information, the synthesis problems for CTL and CTL * are complete for EXPTIME and 2EXPTIME, respectively. (shrink)

Following increasing public concern over the ethical and social implications of contemporary technology, computer science departments around the world have recently increased their efforts to incorporate ethics into their educational curriculum. For our redesigned undergraduate course on Computer Ethics at Rice University, in addition to teaching variety of fundamental ethical theories and approaches to technology, we also sought to emphasize the role of “social” technologies in mediating moral relations and to encourage students to consider moral decision-making, rather than as an (...) abstract rational process, as matter of affective care. To help us achieve this educational objective and inspired by the work of artist Jenny Odell, we designed an activity for students to practice focusing “deep” attention both on themselves and others. In this article, we describe in detail our rationale for this activity, report on lessons learned, and discuss potential applications for this activity in regard to the ongoing online teaching environment following the Covid-19 pandemic. (shrink)

In 1960, E. P. Wigner, a joint winner of the 1963 Nobel Prize for Physics, published a paper titled On the Unreasonable Effectiveness of Mathematics in the Natural Sciences [61]. This paper can be construed as an examination and affirmation of Galileo's tenet that “The book of nature is written in the language of mathematics”. To this effect, Wigner presented a large number of examples that demonstrate the effectiveness of mathematics in accurately describing physical phenomena. Wigner viewed these examples as (...) illustrations of what he called the empirical law of epistemology, which asserts that the mathematical formulation of the laws of nature is both appropriate and accurate, and that mathematics is actually the correct language for formulating the laws of nature. At the same time, Wigner pointed out that the reasons for the success of mathematics in the natural sciences are not completely understood; in fact, he went as far as asserting that “… the enormous usefulness of mathematics in the natural sciences is something bordering on the mysterious and there is no rational explanation for it.”. (shrink)

We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...) model. Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink)

We describe BDD-based decision procedures for the modal logic K. Our approach is inspired by the automata-theoretic approach, but we avoid explicit automata construction. Instead, we compute certain fixpoints of a set of types — which can be viewed as an on-the-fly emptiness of the automaton. We use BDDs to represent and manipulate such type sets, and investigate different kinds of representations as well as a “level-based” representation scheme. The latter turns out to speed up construction and reduce memory consumption (...) considerably. We also study the effect of formula simplification on our decision procedures. To prove the viability of our approach, we compare our approach with a representative selection of other approaches, including a translation of K to QBF. Our results indicate that the BDD-based approach dominates for modally heavy formulae, while search-based approaches dominate for propositionally heavy formulae. (shrink)

In the automata-theoretic approach to verification, we translate specifications to automata. Complexity considerations motivate the distinction between different types of automata. Already in the 60s, it was known that deterministic Büchi word automata are less expressive than nondeterministic Büchi word automata. The proof is easy and can be stated in a few lines. In the late 60s, Rabin proved that Büchi tree automata are less expressive than Rabin tree automata. This proof is much harder. In this work we relate the (...) expressiveness gap between deterministic and nondeterministic Büchi word automata and the expressiveness gap between Büchi and Rabin tree automata. We consider tree automata that recognize derived languages. For a word language L, the derived language of L, denoted L, is the set of all trees all of whose paths are in L. Since often we want to specify that all the computations of the program satisfy some property, the interest in derived languages is clear. Our main result shows that L is recognizable by a nondeterministic Büchi word automaton but not by a deterministic Büchi word automaton iff L is recognizable by a Rabin tree automaton and not by a Büchi tree automaton. Our result provides a simple explanation for the expressiveness gap between Büchi and Rabin tree automata. Since the gap between deterministic and nondeterministic Büchi word automata is well understood, our result also provides a characterization of derived languages that can be recognized by Büchi tree automata. Finally, it also provides an exponential determinization of Büchi tree automata that recognize derived languages. (shrink)

This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and infinitary logics (...) to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful way to analyze the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the application of logic to computer science. (shrink)

Reasoning About Knowledge is the first book to provide a general discussion of approaches to reasoning about knowledge and its applications to distributed ...

We interpret the (formal) postulates of measurement in quantum theory in terms of measurement procedures that can be done in the laboratory (at least in principle).

This article isolates ten prepositions, which constitute the undercurrent paradigm of contemporary discourse of health disease and medicine. Discussion of the interrelationship between those prepositions leads to a systematic refutation of this paradigm. An alternative set is being forwarded. The key notions of the existing paradigm are that health is the natural condition of humankind and that disease is a deviance from that nature. Natural things are harmonious and healthy while human made artifacts are coercive interference with natural balance. It (...) is suggested that the current paradigm is influenced by the world of finances and by instrumental reason. The alternative model suggests that human nature cannot be delineated. Humans fashion their own selves and nature by artificial means, medicine among them. The article discusses the implications of the paradigm adapted in various scholarly and popular debates such as the use of sex hormones for contraception, the care of the elderly, holistic medicine and distributive justice in health care. Medicine is not an isolated or a privileged realm. There is no unique entitlement to health care. It is always part of a broader agenda of social values and institutions. A open view of human societies, values and practices as they are situated within concrete material conditions is the platform required for an integrative and creative discourse of health care. (shrink)

The article calls for a departure from the common concept of autonomy in two significant ways: it argues for the supremacy of semantic understanding over procedure, and claims that clinicians are morally obliged to make a strong effort to persuade patients to accept medical advice. We interpret the value of autonomy as derived from the right persons have to respect, as agents who can argue, persuade and be persuaded in matters of utmost personal significance such as decisions about medical care. (...) Hence, autonomy should and could be respected only after such an attempt has been made. Understanding suffering to a significant degree is a prerequisite to sincere efforts of persuasion. It is claimed that a modified and pragmatic form of discourse is the necessary framework for understanding suffering and for compassionately interacting with the frail. (shrink)

Contrary to the common view, this paper suggests that the Hippocratic oath does not directly refer to the controversial subjects of euthanasia and abortion. We interpret the oath in the context of establishing trust in medicine through departure from Pantagruelism. Pantagruelism is coined after Rabelais' classic novel Gargantua and Pantagruel. His satire about a wonder herb, Pantagruelion, is actually a sophisticated model of anti-medicine in which absence of independent moral values and of properly conducted research fashion a flagrant over-medicalization of (...) human problems. Ultimately this undermines the therapeutic core of medicine itself. We contend that PAS is a case of such over-medicalization and that its institution creates medicophobia. This article does not express an opinion about euthanasia in general. Rather, we claim that physicians should learn from the oath and from Rabelais that they should keep their practice to medical care and not to exploit their expertise and social privileges for the sake of ulterior motives, even when their patients desire those goals. (shrink)

If K is an index of relative voting power for simple voting games, the bicameral postulate requires that the distribution of K -power within a voting assembly, as measured by the ratios of the powers of the voters, be independent of whether the assembly is viewed as a separate legislature or as one chamber of a bicameral system, provided that there are no voters common to both chambers. We argue that a reasonable index – if it is to be used (...) as a tool for analysing abstract, ‘uninhabited’ decision rules – should satisfy this postulate. We show that, among known indices, only the Banzhaf measure does so. Moreover, the Shapley–Shubik, Deegan–Packel and Johnston indices sometimes witness a reversal under these circumstances, with voter x ‘less powerful’ than y when measured in the simple voting game G1 , but ‘more powerful’ than y when G1 is ‘bicamerally joined’ with a second chamber G2 . Thus these three indices violate a weaker, and correspondingly more compelling, form of the bicameral postulate. It is also shown that these indices are not always co-monotonic with the Banzhaf index and that as a result they infringe another intuitively plausible condition – the price monotonicity condition. We discuss implications of these findings, in light of recent work showing that only the Shapley–Shubik index, among known measures, satisfies another compelling principle known as the bloc postulate. We also propose a distinction between two separate aspects of voting power: power as share in a fixed purse (P-power) and power as influence (I-power). (shrink)

Challenges the contemporary materialist and post-truth world view and provides a challenging alternative.

Depression is associated with increased maintenance of negative affect (NA) and reduced – blunted and short-lived – maintenance of positive affect (PA). Studies have focused on factors associated with the maintenance of NA, specifically, the emotion regulation strategy of brooding and the capacity to hold negative affective experiences in working memory (WM). Despite its theoretical importance, less attention has been given to factors associated with the maintenance of PA in depression. This study aims to synthesise factors playing a role in (...) the maintenance of both NA and PA. Specifically, we used self-reported assessment of PA and NA regulation and performance-based measures of NA and PA processing in WM to predict depressive symptoms severity. Participants (N = 219) completed the Affective Maintenance Task (AMT, Mikels et al., Citation2008), which provided performance-based measures of PA and NA maintenance, and filled out questionnaires assessing brooding, positive rumination and depressive severity. Brooding, positive rumination and AMT-based measures of positive (but not negative) affective information processing were independently associated with depressive symptoms. We highlight the unique contributions of PA processing, as well as of self-reported emotion regulation strategies in understanding depression maintenance. (shrink)

"In the gorgeous and rugged terrain of Jewish thought, there is no higher mountain to climb than Maimonides, and no more slippery or exhilarating ascent. Halbertal has made it all the way to the top, and his survey of the whole of the Maimonidean landscape is trustworthy and masterful. This is the richest and most intellectually sophisticated book on Maimonides I have ever read."--Leon Wieseltier "In this learned and penetrating work, Halbertal offers us a Maimonides who draws on the dominant (...) Greco-Islamic thought of his time while creating a system of thought that is fully Jewish. He shows us how the early "Commentary on the Mishnah" links up with the "Mishneh Torah" and with the "Guide of the Perplexed," written at the end of his life, to form an unexpected and radical intellectual unity. Beautifully written, "Maimonides" brings out both Maimonides's intellectual success and the paradoxical critical approaches to him after his death."--David J. Wasserstein, Vanderbilt University "Insightful and learned. Halbertal is perhaps the leading philosopher of Jewish law today. His book on Maimonides, like his other writings, reflects wide erudition and is written clearly and sharply."--Warren Zev Harvey, professor emeritus, Hebrew University of Jerusalem "Displaying the marvelous depth and clarity that mark all his work, Halbertal explains in abundant detail the transformations that Maimonides sought to effect in the Jewish world. He provides incisive interpretations of both legal and philosophical writings, yet he is also a biographer, binding together Maimonides's life, self-perception, and intellectual agenda. This is an exceptionally rich book, one that offers fresh perspectives for experts and a highly accessible introduction for general readers."--David Shatz, Yeshiva University "An outstanding and thrilling portrait of Maimonides. Halbertal's analytic lucidity and psychological depth are singular, and his talents are abundantly apparent on every page. This is an extraordinary book."--Menachem Lorberbaum, Tel Aviv University. (shrink)

In the latter part of the fifteenth century, a Jewish translator, working together with a Slavic amanuensis, translated into the East Slavic language of the Grand Duchy of Lithuania three medieval Hebrew translations of Arabic philosophical texts: the Logical Terminology, a short work on logic attributed to Maimonides (but probably by a different medieval Jewish author); and two sections of the Muslim theologian Al-Ghazali's famous Intentions of the Philosophers. Highlighting the unexpected role played by Jewish translators as agents of cultural (...) transmission in the heady messianic atmosphere leading up to the year 1492, these texts drew the attention of the Orthodox Church authorities as being in the possession of the enlightened heretical sect known as the Judaizers, which had emerged in Novgorod and spread to Moscow. Reflecting three and even four layers of translation, Prof. Moshe Taube's new triple-language critical edition of the Logika of the Judaizers displays the Slavic texts alongside the Hebrew translations on which they are based and accompanies them with a modern English translation. In his comprehensive introduction and commentary, Taube surveys earlier scholarly efforts to identify the provenance and purport of the translations, discusses the linguistic and textological issues raised by these early Ruthenian texts, puts forward the likely dissimilar motivations of the Jewish translator and the Christians who commissioned the work, and reveals the translator's probable identity. The present publication, a long-awaited desideratum, will be of interest not only to historians of the Great Duchy of Lithuania and of the principality of Muscovy, but also to scholars of Jewish history and of the history of philosophy and science, as well as to linguists studying the history of the Belorussian, Ukrainian and Russian languages. (shrink)

This volume of essays examines key themes in Jewish philosophy and ethics from the rigorous perspective of philosophical analysis. The first set of essays takes up the challenge of living a Jewish life, and includes essays on pleasure, joy, human suffering, Jewish ritual practice and the philosophical life. The second set of essays analyzes the value and meaning of autonomy, human freedom and tolerance in Jewish thought, crucial themes in western political thought and life. Other essays in the volume examine (...) the many meanings of Jewish texts, and such crucial issues in applied Jewish ethics as ecology, medical ethics, and justified homicide. Finally, a number of essays plumb the depths of one of the most influential and creative Jewish thinkers of the twentieth century, Rabbi Joseph B. Soloveitchik. Taken as a whole, this volume advances the engagement of classical Jewish themes with Anglo-American philosophy, shedding new light both on the Jewish tradition, and on the western philosophical enterprise. (shrink)

In Judaism Straight Up, Moshe Koppel explores the central differences between traditional societies--including traditional Judaism--and contemporary cosmopolitan ones. He explains everything you always wanted to know about the subtleties of Jewish morality, tradition, and belief, and how these have unfolded to beat cosmopolitanism at its own game: advancing cooperation, fairness, and freedom. Written with incisiveness and droll wit--and a scientific sensibility that draws on economics, game theory, and other disciplines--Judaism Straight Up reveals the secret of Jewish traditionalism's endurance."--Page [4] (...) of cover. (shrink)