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

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)

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

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)

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)

Sahip olduğu akademik imkânların ve başta İngilizce olmak üzere birçok dilde uluslararası yayınların çokluğu nedeniyle Amerika Birleşik Devletleri’ndeki İslam çalışmaları yoğun, üretken ve dünya genelinde ilgiyle takip edilen bir alandır. Ancak Batı’daki üniversitelerin genelinde olduğu gibi Amerikan üniversitelerinde de İslam felsefesi/tarihi çalışmaları oldukça zayıftır. Bu makalede öncelikle geçmişten günümüze İslam çalışmalarının ABD’deki durumu tasviri bir metotla ortaya konulmakta ve İslam Felsefesinin ABD’deki İslam çalışmaları içerisindeki zayıf konumu sorgulanmaktadır. İkinci olarak Post-Oryantalist süreçte İslam Felsefesi çalışmalarında öne çıkan isimler ve çalışmaları değerlendirilmektedir. (...) Sonuç olarak ABD üniversite sisteminin genel yapısının gereği olarak İslam Felsefesi çalışmaları nicelik bakımından Avrupa ve İslam coğrafyasından daha zayıf olduğu görülmektedir. Bu durumu iki şekilde açıklamak mümkündür. Birincisi alanın Amerikan devlet felsefesinin temel ilkesi olan bilgi-güç hedefi ve alanın politik çıkarlarıyla ilişkisinin zayıflığıdır. Bu durum Post-Oryantalist eğilimin arka planını da oluşturmaktadır. İkincisi ise fenomenolojist yönteme olan ilginin artması ve Amerikan yükseköğretim sisteminde hâkim olan kozmopolitanizm ve interdisiplinerci yaklaşımlardır.Özet: Dünyanın önde gelen üniversitelerinde İslam çalışmaları ve bu çalışmalar içerisinde yer alan İslam felsefesi çalışmalarının önemli bir akademik ilgi alanı olduğu görülmektedir. Bu ilgi ABD’de de yaklaşık 150 yıllık bir geçmişe sahiptir. Son yıllarda Amerika Birleşik Devletleri’nde İslam çalışmalarında sadece ciddi bir artış değil aynı zamanda çeşitlenme de söz konusu olmuştur. ABD’deki İslam çalışmaları ve özelde İslam felsefesi çalışmalarının durumunu birlikte ele alan akademik araştırmalar ise henüz bulunmamaktadır. Son gelişmeleri de dikkate alarak alanla ilgili araştırmaların sürdürülmesi ve İslam felsefesi çalışmalarının da noksan bırakılan izinin sürülmesi gerekmektedir. Bu noktadan hareketle bu makale çalışması, üniversite müfredatlarıyla ilgili araştırmalar, web taramaları ve yazılı materyaller üzerinden gerçekleştirilecek ve ilgili kitaplar, makaleler ve diğer kaynaklar taranarak konu hakkında deskriptif bilgiler sunulacaktır. Bu yöntemin tercih edilme nedeni derinlemesine bir araştırmadan daha çok genel resmi ortaya koymak ve mevcut durum hakkında bilgi vermektir. Sahanın genişliği ve kaynakların çeşitliliği ve konunun daha özel ve yoğun bir çalışma gerektiren yapısı nedeniyle diğer yöntemler tercih edilmemiştir Çalışma iki ana başlıktan oluşmaktadır. Birincisi ABD’deki İslam çalışmalarının konumu ile ilgilidir. Bu başlık altında 18. yüzyıldan itibaren İslam çalışmalarının ABD’deki seyri hakkında bilgi verilmekte ve İslam çalışmalarının günümüzdeki konumu detaylandırılmaktadır. İkinci başlık İslam Felsefesi çalışmalarının İslam çalışmaları içerisindeki ve ABD akademilerindeki konumuyla ilgilidir. Bu başlık altında İslam Felsefesi çalışmalarının geçmişten günümüze kadar gelinen süreçte geçirdiği evreler tasvir edilmekte ve bazı isimlerin ve eserlerinin değerlendirmesi yapılmaktır. İncelemeler sonucunda ABD’deki İslam çalışmalarının geçmişinin yaklaşık 150 yıla tekabül etmesine rağmen yeterli seviyeye ulaşmadığı görüldü. Hâlbuki sahip olduğu Müslüman nüfus, akademik imkânlar ve başta İngilizce olmak üzere birçok dilde uluslararası yayınların çokluğu nedeniyle ABD’deki İslam çalışmalarının beklenenden daha yoğun, üretken olması beklenirdi. Ancak buna rağmen Daha çok Fenomenolojist ve İnterdisipliner yaklaşımın tercih edildiği Amerikan üniversitelerinin akademik kadro çeşitliliği ve başta İngilizce olmak üzere farklı dillerdeki yayın yelpazesinin genişliği ve son yıllarda yeni bir durum olan sosyal medyaya açık akademik faaliyetler ABD’nin İslam çalışmaları alanındaki etkinliğini giderek arttırmaktadır. Geçmişte İslam çalışmalarında öncü rolü oynayan İngiltere, Fransa, Almanya ve Hollanda gibi ülkelerde öteden beri oryantalist eğilimi temsil eden bu tür çalışmalar günümüz ABD üniversitelerinde interdisipliner ve multidisipliner bir format kazarak devam etmektedir. ABD’deki İslam çalışmaları üzerinde yoğunlaşan akademik çalışmalara göre İslam çalışmalarına yön veren en önemli etken oryantalist eğilimlerdir. Bunun yanında 11 Eylül olaylarının sonucunda da artan bir ilgiden söz etmek gerekmektedir. Bu ilgi sadece alanda yeni istihdam imkânlarının oluşmasına değil aynı zamanda araştırmacı sayısının da artmasına neden olmuştur. Çalışmamın ikinci kısmını oluşturan ABD üniversitelerindeki İslam felsefesi çalışmalarının genel durumuna bakılacak olursa bu çalışmaların sosyoloji, antropoloji ve kültür çalışmaları gibi alanlarda görülen çeşitliliğe de sahip olduğunu söylemek oldukça zordur. ABD üniversitelerindeki İslam felsefesi çalışmaları İslam çalışmaları genel çatısı altında sürdürülmektedir. Bu alandaki çalışmalar başlarda daha çok oryantalist eğilimi temsil eden Philip Hittî, Leo Strauss, Muhsin Mehdî, Fazlurrahmân, İsmâil Râci Fârukî, Mâcid Haddûrî, Moshe Pearlmann, gibi önemli isimler tarafından sürdürülmekteydi. Günümüzde Charles Butterworth, Seyyid Hüseyin Nasr, Oliver Leaman, Dimitri Gutas, Robert Wisnovsky, Frank Griffel, John Walbridge ve daha birçok isim yeni eğilimin temsilcileri olarak alanla ilgili çalışmalarını sürdürmektedir. Bu araştırmacılar, Amerikan akademik siteminin bir sonucu olarak sadece İslam felsefesi değil aynı zamanda İslam bilim tarihi, İslam tarihi ve medeniyeti, İslam ve Batı vb. alanlarda da yayınlar yapmakta ve İslam çalışmalarının sürdürüldüğü çeşitli üniversitelerde dersler vermekte ve lisansüstü seviyede öğrenciler yetiştirmektedir. Bu noktadan hareketle diyebiliriz ki İslam felsefesi çalışmaları ise diğer İslam çalışmalarına kıyasla daha da zayıftır. Bu durumun sebeplerini şu şekilde açıklamak mümkündür:1-Amerikan devlet felsefesinin temel ilkesi olan bilgi-güç hedefi ve alanın politik çıkarlarıyla ilişkisinin zayıflığı. Bilimlerle kurulan bu politik çıkar ilişkisi Post-Oryantalist eğilimin arka planını da oluşturmaktadır. 2-Amerikan Üniversitelerinde fenomenolojist yönteme olan ilginin artması ve Amerikan yükseköğretim sisteminde hâkim olan kozmopolitanizm ve interdisiplinerci yaklaşımlar.3-Amerikan üniversitelerindeki Yakın Doğu, Ortadoğu ve İslam Çalışmalarında İslam felsefesi dersleri felsefenin ya da felsefe tarihinin bir parçası olarak müfredatta yer alması. Amerikan üniversitelerinde standart müfredat sistemi yaygın olmadığından İslam felsefesi ile ilgili dersler bölümden daha çok ders veren hocanın ilgisine ve isteğine bağlı olarak verilmektedir.4-Kıta Avrupası’nda görülen katı oryantalist eğilimlerin nisbeten azlığı ve ABD devlet politikalarının gereği olarak şekillenen havuz usulü müfredat.5-Bazı İslam felsefesi uzmanlarının alanı terk ederek daha çok aktüel tartışmalara yönelmesi ve daha çok Müslümanların geri kalmışlığı sorunundan hareketle üretilen problemlere odaklanması. Son olarak İslam felsefesi çalışmaları Müslümanların genelinin ilgilendiği bir disiplin olmadığı için üniversite dışında İslam felsefesi çalışmalarının yürütüldüğü kurumsal yapılar ABD’de de henüz teşekkül etmemiştir. Bazı bölümlerde İslam Felsefesi İslam düşüncesi tarihinin bir alt dalı olarak varlığını sürdürmektedir. Ancak İslam felsefesi müstakil bir alan olarak kendisine henüz ABD üniversitelerinde yer bulamamıştır. USA’da artan İslam çalışmalarının yeterli düzeyde olmasa da dünyadaki islam çalışmalarına yön verebilecek noktaya ulaştığını söylemek mümkündür. (shrink)

Responsibility is a central juridical, moral and social concept that calls on individuals to act in ways that are necessary and morally right. It represents a fundamental normative relationship that bridges abstract philosophical ideas with empirical social realities. Despite its everyday importance, the derivation and application of responsibility are complex and often contested. This article explores the meaning and conditions under which responsibility can be justifiably demanded, as well as its practical enforceability. Responsibility is understood as a normative relationship with (...) both moral and legal dimensions, constructed through social interactions. A responsible practice requires intersubjective agreement on the reasons and motives for actions, enabling the formulation and implementation of ethical justifications. (shrink)