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)

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)

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)

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)

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

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)

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 book constitutes the refereed proceedings of the 10th International Conference on Logic Programming, Artificial Intelligence, and Reasoning, LPAR 2003, held in Almaty, Kazakhstan in September 2003. The 27 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 65 submissions. The papers address all current issues in logic programming, automated reasoning, and AI logics in particular description logics, proof theory, logic calculi, formal verification, model theory, game theory, automata, proof search, constraint systems, model checking, (...) and proof construction. (shrink)

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)

The first part of this study offers a synoptic overview of Alfonso de la Torre’s selective engagement with Maimonidean philosophy in the first part of his Visión Deleitable. Our analysis is complemented with some comparative notes on the reception of Maimonides’s thought in late medieval Spain. Visión Deleitabl e’s fate will be examined in comparison to two other 15th century works of Jewish or converso authorship that also broached the Guide for the Perplexed for the benefit of Christian readers: the (...) Old Spanish translation of Maimonides’s Guide by Pedro de Toledo and Moshe Arragel’s commentary on his Bible translation for the Christian Master of Calatrava, don Luis de Guzmán. (shrink)

This paper investigates the formal relationship between two prominent approaches to the logic of belief change. The first one uses the idea of "relational partial meet contractions" as developed by Alchourrón, Gärdenfors and Makinson (Journal of Symbolic Logic 1985), the second one uses the concept of "epistemic entrenchment" as elaborated by Gärdenfors and Makinson (in Theoretical Aspects of Reasoning about Knowledge, M. Y. Vardi, Los Altos 1988). The two approaches are shown to be strictly equivalent via direct links between (...) the underlying formal relations. The paper closes with observations about the application of epistemic entrenchment to simple and iterated revisions. (shrink)

La Meditación de la técnica contiene las reflexiones de José Ortega y Gasset sobre un fenómeno de invasora presencia en el mundo contemporáneo. Trata, en suma, de inscribir el hecho de la técnica en el marco de una antropología filosófica, fundada en el sistema orteguiano, para así contribuir a la comprensión del momento histórico contemporáneo. El volumen incluye, además del curso ¿Qué es la técnica?, desarrollado en 1933 en la Universidad de Santander, otros textos afines: la conferencia El mito del (...) hombre allende a la técnica pronuncida en Darmstadt y varios ensayos sobre el conocimiento científico, que prueban la permanente atención que Ortega prestó a las novedades de la ciencia contemporánea. En esta nueva edición el texto se ha revisado y corregido conforme a los manuscritos originales o las primeras ediciones. La principal novedad es una Introducción al curso ¿Qué es la técnica?, sólo editada póstumamente. (shrink)

The Mesillas Yesharim / Path of the Just was the masterpiece of Rabbi Moshe Chaim Luzzatto, the great mystic, philosopher, sage, and saint. For centuries, this classic text for better living has been every man's primer for ideal life. Wherever there were Jews there was a well-thumbed Mesillas Yesharim. In this book, Rabbi Twerski applies the text and themes of Mesillas Yesharim to the everyday challenges of the 90s. He shows us how we can succeed in the quest for (...) a better life and in bettering ourselves. (shrink)

I have found that religious philosophers sometimes commit what might be called the fallacy of misplaced argumentation. Permit me to explain. Any fully developed system of thought contains many assertions about the world. Yet this proliferation of assertions can be traced back to several underlying propositions which are their logical forebears. This is because large-scale theories generally grow out of fundamental intuitions or conceptual stances. These fundamental intuitions become formulated into theory-embedded, second-order propositions. Understanding the centrality of second-order propositions is (...) essential to understanding the theory which they generate, with its numerous first-order assertions about the world. (shrink)

Desde 1935 Ortega anunció la publicación de un libro con el título de El hombre y la gente contendría su doctrina sociológica, pero sólo se publicó en 1957 y como la primera de sus obras póstumas. Esta nueva edición incluye el texto, inédito hasta la fecha, de la conferencia pronunciada por Ortega en 1934 a la que había dado el título que hoy lleva este libro, y en la que por primera vez expuso públicamente su idea de los " usos (...) " como realidad constitutiva del hecho social. Por otra parte, el texto va revisado y cotejado conforme a los originales. (shrink)

Answers to the questions of what justifies conscientious objection in medicine in general and which specific objections should be respected have proven to be elusive. In this paper, I develop a new framework for conscientious objection in medicine that is based on the idea that conscience can express true moral claims. I draw on one of the historical roots, found in Adam Smith’s impartial spectator account, of the idea that an agent’s conscience can determine the correct moral norms, even if (...) the agent’s society has endorsed different norms. In particular, I argue that when a medical professional is reasoning from the standpoint of an impartial spectator, his or her claims of conscience are true, or at least approximate moral truth to the greatest degree possible for creatures like us, and should thus be respected. In addition to providing a justification for conscientious objection in medicine by appealing to the potential truth of the objection, the account advances the debate regarding the integrity and toleration justifications for conscientious objection, since the standard of the impartial spectator specifies the boundaries of legitimate appeals to moral integrity and toleration. The impartial spectator also provides a standpoint of shared deliberation and public reasons, from which a conscientious objector can make their case in terms that other people who adopt this standpoint can and should accept, thus offering a standard fitting to liberal democracies. (shrink)

Questionnaire data obtained from 97 supervisory and nonsupervisory employees representing the Production, Production Services, Marketing, and Administration departments of an Israeli metal production plant were used to test the relationship between selected personal and organizational attributes and work related misbehavior. Following Vardi and Wiener''s (1996) framework, Organizational Misbehavior (OMB) was defined as intentional acts that violate formal core organizational rules. We found that there was a significant negative relationship between Organizational Climate and OMB, and between the Organizational Climate dimensions (...) (Warmth and Support, and Reward), and OMB. Also, the activities of misbehavior reported by both managers and employees were negatively related to the Rules, Instrumental and Caring dimensions of Ethical Climates as defined by Victor and Cullen (1988). (shrink)

Abstract: An experiment is reported on the effects of a moral education programme in schools. Children were pretested on Kohlberg's index of level of moral thinking. The experimental group was then given twelve hours of discussion of moral problems other than those used in Kolhberg's test spread over twelve weeks. Subsequent testing showed that the experimental group had had tended to move towards a higher level of thinking when compared with controls.

The literature on conscientious objection in medicine presents two key problems that remain unresolved: Which conscientious objections in medicine are justified, if it is not feasible for individual medical practitioners to conclusively demonstrate the genuineness or reasonableness of their objections? How does one respect both medical practitioners’ claims of conscience and patients’ interests, without leaving practitioners complicit in perceived or actual wrongdoing? My aim in this paper is to offer a new framework for conscientious objections in medicine, which, by bringing (...) medical professionals’ conscientious objection into the public realm, solves the justification and complicity problems. In particular, I will argue that: an “Uber Conscientious Objection in Medicine Committee” —which includes representatives from the medical community and from other professions, as well as from various religions and from the patient population—should assess various well-known conscientious objections in medicine in terms of public reason and decide which conscientious objections should be permitted, without hearing out individual conscientious objectors; medical practitioners should advertise their conscientious objections, ahead of time, in an online database that would be easily accessible to the public, without being required, in most cases, to refer patients to non-objecting practitioners. (shrink)