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)

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

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 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)

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)

Moshe Idel, Cabalistii nocturni Traducere de Ana-Elena Ilinca, Ed. Provopress, Cluj-Napoca, 2005.

Physicians frequently ask whether they should give patients what they want, usually when there are considerations pointing against doing so, such as medicine’s values and physicians’ obligations. It has been argued that the source of medicine’s values and physicians’ obligations lies in what has been dubbed “the internal morality of medicine”: medicine is a practice with an end and norms that are definitive of this practice and that determine what physicians ought to do qua physicians. In this paper, I defend (...) the claim that medicine requires a morality that is internal to its practice, while rejecting the prevalent characterization of this morality and offering an alternative one. My approach to the internal morality of medicine is constructivist in nature: the norms of medicine are constructed by medical professionals, other professionals, and patients, given medicine’s end of “benefitting patients in need of prima facie medical treatment and care.” I make the case that patients should be involved in the construction of medicine’s morality not only because they have knowledge that is relevant to the internal morality of medicine—namely, their own values and preferences—but also because medicine is an inherently relational enterprise: in medicine the relationship between physician and patient is a constitutive component of the craft itself. The framework I propose provides an authoritative morality for medicine, while allowing for the incorporation, into that very morality, of qualified deference to patient values. (shrink)

Moshe Idel, Cabalistii nocturni Editura Provopress, Cluj-Napoca, 2005, 81 pp.

The article discusses the contribution of Moshe Idel’s vast research to the field of religious studies. The terms which best capture his overall approach are “plurality” and “complexity”. As a result, Idel rejects essentialist definitions of “Judaism”, or any other religious tradition. The ensuing question is: to what extent does his approach allow for the characterization of Judaism as a singular phenomenon which can be differentiated from other religions? The answer seems to lie in Idel’s definition of the “connectivity” (...) between the human and the divine as a relationship which “underlies the basic notion of religion as such”. Opposing Rudolph Otto’s description of the holy as remote, Idel explains holiness in terms of closeness and connection. This reading of religion is supported by that of sociologist Daniéle Hervieu-Léger, who describes religious practice as constructing a “chain of memory” - a term which echoes with Idel’s analysis of Jewish ritual as the construction of “enchanted chains” of connectivity. Hervieu-Léger’s study points towards the possibility of regarding Judaism, as a family-centered tradition, as paradigmatic for traditional religion. Indeed, in recent studies, Idel describes the construction of memory through ritual practice as the most important means of shaping identity for all forms of traditional Judaism. The model of “chains of memory” can be located in classical Jewish texts, such as a much-quoted passage by Nahmanidies - the extremely important thirteenth-century Kabbalist and legal authority. This text describes Jewish rituals as maintaining continuity across generations. We see then that the notion of connectivity moves us closer to the concerns found in central Jewish texts, rather than imposing modern agenda on them. It can also be used to determine to what extent a given idea or practice is connected to the chain of connectivity constructed by a given tradition or is rather tangential to it. In this sense, it is a corrective to the danger of “dispersion” that is implicit in Idel’s focus on plurality and complexity. (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)

La Filosofía del Derecho contemporánea plantea retos importantes, que según Carla Faralli se sistematizan en dos. Por una parte, la apertura a los hechos; y por otra a los valores políticos y éticos. La tradicional conversación del iusnaturalismo con positivismo y el realismo jurídico parece haber sido superada, especialmente después de la obra de Hart. Y en este periodo, lo cierto es que las consecuencias del realismo jurídico han derivado en modos de proponer el concepto, aplicación e interpretación del Derecho, (...) mas ajustados con la realidad. En este sentido, la apertura a la economía, protagonizada por el análisis económico del Derecho; la critica abierta al análisis económico llevada a cabo por el movimiento Critical legal Studies; y las argumentaciones de Derecho y Literatura ofrecen alternativas importantes, que se analizan en este articulo. (shrink)

En este artículo tratamos sobre los aspectos empíricos y conceptuales en la Genética Mendeliana y analizamos los vínculos entre ellos. Primero discutimos las ventajas de una representación gráfica de las teorías empíricas; luego pormenorizamos la estructura conceptual de la genécica; en seguida, esquematizamos su protocolo experimental, a continuación destacamos los engarces entre ambas representaciones y, por último, proporcionamos una caracterización holista de la práctica genética, donde el representar y el intervenir se encucntran entremezclados.In this article we deal with the conceptual (...) and empirical features of Mendelian Genetics, and analyze the links between them. First we discuss the challenges of portraying empirical theories as graphical representations. We then give a detailed account of the conceptual structure underlying Mendelian Genetics, followed by a schematization of the experimental protocol involved in this line of research. Links between both representations are highlighted. Finally, we provide a holistic characterization of Mendelian practice, where representing and intervening are intertwined. (shrink)

El 30 de julio de 1916 se eligieron los representantes para la Convención encargada de elaborar la segunda constitución uruguaya que fijó las reglas de la naciente democracia. En esta elección se utilizaron por primera vez el voto secreto y una versión inédita de representación proporcional. Para explicar por qué se usaron esas reglas y no otras, se utiliza la teoría de los órdenes sociales de Emanuel Adler. Las nuevas reglas recogen en el plano institucional la evolución cognitiva de caudillos (...) y doctores, los protagonistas centrales de la comunidad de práctica democrática uruguaya. Los caudillos fueron aprendiendo en la práctica, por ensayo y error, a competir por el poder pero también a pactar. Los doctores, a partir de esas prácticas pero también de las teorías que circulaban en la época, aportaron el conocimiento reflexivo que recogieron las nuevas normas. De todos modos, no es posible comprender la trayectoria doméstica sin tomar en cuenta la influencia de procesos exógenos. La Convención de Buenos Aires y la Ley Sáenz-Peña tuvieron un impacto profundo en Uruguay. (shrink)