The standard style of argument used to prove that a theory is unde- cidable relies on certain consistency assumptions, usually that some fragment or other is negation consistent. In a non-paraconsistent set- ting, this amounts to an assumption that the theory is non-trivial, but these diverge when theories are couched in paraconsistent logics. Furthermore, there are general methods for constructing inconsistent models of arithmetic from consistent models, and the theories of such inconsistent models seem likely to differ in terms of (...) complexity. In this paper, I begin to explore this terrain, working, particularly, in incon- sistent theories of arithmetic couched in three-valued paraconsistent logics which have strong (i.e. detaching) conditionals. (shrink)

Let M be a first-order structure; we denote by DEF(M) the set of all first-order definable relations and functions within M. Let π be any one-to-one function from N into the set of prime integers. Let ∣ and $\bullet$ be respectively the divisibility relation and multiplication as function. We show that the sets DEF(N,π,∣) and $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ are equal. However there exists function π such that the set DEF(N,π,∣), or, equivalently, $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ is not equal to $\mathrm{DEF}(\mathbb{N},+,\bullet)$ . Nevertheless, in all cases (...) there is an $\{\pi,\bullet\}$ -definable and hence also {π,∣}-definable structure over N which is isomorphic to $\langle\mathbb{N},+,\bullet\rangle$ . Hence theories TH(N,π,∣) and $\mathrm{TH}(\mathbb{N},\pi,\bullet)$ are undecidable. The binary relation of equipotence between two positive integers saying that they have equal number of prime divisors is not definable within the divisibility lattice over positive integers. We prove it first by comparing the lower bound of the computational complexity of the additive theory of positive integers and of the upper bound of the computational complexity of the theory of the mentioned lattice. The last section provides a self-contained alternative proof of this latter result based on a decision method linked to an elimination of quantifiers via specific tables. (shrink)

Speakers’ perception of a visual scene influences the language they use to describe it—which objects they choose to mention and how they characterize the relationships between them. We show that visual complexity can either delay or facilitate description generation, depending on how much disambiguating information is required and how useful the scene's complexity can be in providing, for example, helpful landmarks. To do so, we measure speech onset times, eye gaze, and utterance content in a reference production experiment (...) in which the target object is either unique or non-unique in a visual scene of varying size and complexity. Speakers delay speech onset if the target object is non-unique and requires disambiguation, and we argue that this reflects the cost of deciding on a high-level strategy for describing it. The eye-tracking data demonstrate that these delays increase when speakers are able to conduct an extensive early visual search, implying that when speakers scan too little of the scene early on, they may decide to begin speaking before becoming aware that their description is underspecified. Speakers’ content choices reflect the visual makeup of the scene—the number of distractors present and the availability of useful landmarks. Our results highlight the complex role of visual perception in reference production, showing that speakers can make good use of complexity in ways that reflect their visual processing of the scene. (shrink)

Fluted Logic is essentially first-order predicate logic deprived of variables. The lack of variables results in reduced expressiveness. Nevertheless, many logical problems that can be stated in natural language, such as the famous Schubert's Steamroller, can be rendered in fluted logic. Further evidence of the expressiveness of fluted logic is its close relation to description logics. Already it has been shown that fluted logic is decidable and has the finite-model property. This paper shows that fluted logic has the exponential-model property (...) and that deciding satisfiability is NEXPTIME-complete. It is shown further that fluted logic is 'nice, that is, it shares with first-order predicate logic the interpolation property and model preservation properties. (shrink)

Fluted Logic is essentially first-order predicate logic deprived of variables. The lack of variables results in reduced expressiveness. Nevertheless, many logical problems that can be stated in natural language, such as the famous Schubert's Steamroller, can be rendered in fluted logic. Further evidence of the expressiveness of fluted logic is its close relation to description logics. Already it has been shown that fluted logic is decidable and has the finite-model property. This paper shows that fluted logic has the exponential-model property (...) and that deciding satisfiability is NEXPTIME-complete. It is shown further that fluted logic is 'nice’, that is, it shares with first-order predicate logic the interpolation property and model preservation properties. (shrink)

I defend the prospect of good science in the social sciences by looking at the obstacles to social laws. I criticize traditional approaches, which rule for or against social laws on primarily conceptual grounds, and argue that only a close analysis of actual empirical research can decide the issue. To that end, I focus on problems caused by the ceteris paribus nature of social generalizations, outline a variety of ways those problems might be handled, and then examine in detail the (...) work of Paige on agrarian revolutions. Paige's work, I argue, handles its problems roughly as well as does some of the best work in evolutionary biology. The upshot is that some social laws can be relatively well confirmed. (shrink)

The ability of ordinary differential equations (ODEs) to simulate discrete machines with a universal computing power indicates a new source of difficulties for event detection problems. Indeed, nearly any kind of event detection is algorithmi- cally undecidable for infinite or finite half-open time intervals, and explicitly given “well-behaved” ODEs (see [18]). Practical event detection, however, usually takes place on finite closed time intervals. In this paper the undecidability of general event detection is extended to such intervals. On the other hand, (...) on finite closed time in- tervals event detection in a certain approximate sense is quite generally decidable, which partly saves the case for practicable event detection. The capability of simulat- ing universal Turing machines is still there, and is used to give complexity lower bounds in terms of accuracy of event detection. The ODEs used here are of course quite complicated, but not artificial, in that even from the point of view of practical event detection it would appear difficult to find criteria to exclude them. (shrink)

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...) when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity. (shrink)

The social intuitionist approach to moral judgments advanced by social psychologist Jonathan Haidt presupposes that it is possible to provide an explanation of the human moral sense without normative implications. By contrast, Iris Murdoch’s philosophical work on moral psychology suggests that every description of morality necessarily involves evaluative features that reveal the thinker’s own moral attitudes and implicit philosophical pictures. In the light of this, we contend that Haidt’s treatment of the story about Julie and Mark, two siblings who decide (...) to have casual, protected, and in his view harmless sex, provides a too simplistic picture of what is involved in understanding human morality. Despite his aim to explain the roots of moral judgments, he fails to provide a deeper understanding of morality in two different respects. First, he does so by suggesting that his story contains all the relevant information needed to take a moral stand on it, and by rejecting as irrelevant the wider human context in which questions about sexual and family relations arise. Second, he simplifies the responses of the people who are subject to his experiment by disregarding their various reasons for disapproving and by equating understanding human morality with explaining an impersonal psychological process. (shrink)

We define a multi-modal version of Computation Tree Logic (CTL) by extending the language with path quantifiers $E^\delta $ and $E^\delta $ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a CTL axiomatisation for each dimension. Completeness is proved by employing the completeness result for CTL to obtain a model along each dimension in turn. We also show that (...) the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for CTL. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional CTL logic. (shrink)

We define a multi-modal version of Computation Tree Logic (ctl) by extending the language with path quantifiers E δ and A δ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a ctl axiomatisation for each dimension. Completeness is proved by employing the completeness result for ctl to obtain a model along each dimension in turn. We also show that (...) the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for ctl. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional ctl logic. (shrink)

We define a multi-modal version of Computation Tree Logic ( ctl ) by extending the language with path quantifiers E δ and A δ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a ctl axiomatisation for each dimension. Completeness is proved by employing the completeness result for ctl to obtain a model along each dimension in turn. We also (...) show that the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for ctl. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional ctl logic. (shrink)

Deliberative analysis enables us to weigh features, simulate futures, and arrive at good, tractable decisions. So why do we so often eschew deliberation, and instead rely on more intuitive, gut responses? We propose that intuition might be prescribed for some decisions because people’s folk theory of decision-making accords a special role to authenticity, which is associated with intuitive choice. Five pre-registered experiments find evidence in favor of this claim. In Experiment 1 (N = 654), we show that participants prescribe intuition (...) and deliberation as a basis for decisions differentially across domains, and that these prescriptions predict reported choice. In Experiment 2 (N = 555), we find that choosing intuitively vs. deliberately leads to different inferences concerning the decision-maker’s commitment and authenticity—with only inferences about the decision-maker’s authenticity showing variation across domains that matches that observed for the prescription of intuition in Experiment 1. In Experiment 3 (N = 631), we replicate our prior results and rule out plausible confounds. Finally, in Experiment 4 (N = 177) and Experiment 5 (N = 526), we find that an experimental manipulation of the importance of authenticity affects the prescribed role for intuition as well as the endorsement of expert human or algorithmic advice. These effects hold beyond previously recognized influences on intuitive vs. deliberative choice, such as computational costs, presumed reliability, objectivity, complexity, and expertise. (shrink)

We define a multi-modal version of Computation Tree Logic (ctl) by extending the language with path quantifiers E δ and A δ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a ctl axiomatisation for each dimension. Completeness is proved by employing the completeness result for ctl to obtain a model along each dimension in turn. We also show that (...) the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for ctl. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional ctl logic. (shrink)

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...) disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

Some things look more complex than others. For example, a crenulate and richly organized leaf may seem more complex than a plain stone. What is the nature of this experience—and why do we have it in the first place? Here, we explore how object complexity serves as an efficiently extracted visual signal that the object merits further exploration. We algorithmically generated a library of geometric shapes and determined their complexity by computing the cumulative surprisal of their internal skeletons—essentially (...) quantifying the “amount of information” within each shape—and then used this approach to ask new questions about the perception of complexity. Experiments 1–3 asked what kind of mental process extracts visual complexity: a slow, deliberate, reflective process (as when we decide that an object is expensive or popular) or a fast, effortless, and automatic process (as when we see that an object is big or blue)? We placed simple and complex objects in visual search arrays and discovered that complex objects were easier to find among simple distractors than simple objects are among complex distractors—a classic search asymmetry indicating that complexity is prioritized in visual processing. Next, we explored the function of complexity: Why do we represent object complexity in the first place? Experiments 4–5 asked subjects to study serially presented objects in a self‐paced manner (for a later memory test); subjects dwelled longer on complex objects than simple objects—even when object shape was completely task‐irrelevant—suggesting a connection between visual complexity and exploratory engagement. Finally, Experiment 6 connected these implicit measures of complexity to explicit judgments. Collectively, these findings suggest that visual complexity is extracted efficiently and automatically, and even arouses a kind of “perceptual curiosity” about objects that encourages subsequent attentional engagement. (shrink)

BackgroundSome people with progressive neurological diseases find they need additional support with eating and drinking at mealtimes, and may require artificial nutrition and hydration. Decisions concerning artificial nutrition and hydration at the end of life are ethically complex, particularly if the individual lacks decision-making capacity. Decisions may concern issues of life and death: weighing the potential for increasing morbidity and prolonging suffering, with potentially shortening life. When individuals lack decision-making capacity, the standard processes of obtaining informed consent for medical interventions (...) are disrupted. Increasingly multi-professional groups are being utilised to make difficult ethical decisions within healthcare. This paper reports upon a service evaluation which examined decision-making within a UK hospital Feeding Issues Multi-Professional Team.MethodsA three month observation of a hospital-based multi-professional team concerning feeding issues, and a one year examination of their records. The key research questions are: a) How are decisions made concerning artificial nutrition for individuals at risk of lacking decision-making capacity? b) What are the key decision-making factors that are balanced? c) Who is involved in the decision-making process?ResultsDecision-making was not a singular decision, but rather involved many different steps. Discussions involving relatives and other clinicians, often took place outside of meetings. Topics of discussion varied but the outcome relied upon balancing the information along four interdependent axes: Risks, burdens and benefits; Treatment goals; Normative ethical values; Interested parties.ConclusionsDecision-making was a dynamic ongoing process with many people involved. The multiple points of decision-making, and the number of people involved with the decision-making process, mean the question of ‘who decides’ cannot be fully answered. There is a potential for anonymity of multiple decision-makers to arise. Decisions in real world clinical practice may not fit precisely into a model of decision-making. The findings from this service evaluation illustrate that within multi-professional team decision-making; decisions may contain elements of both substituted and supported decision-making, and may be better represented as existing upon a continuum. (shrink)

‘First. That on October 23, in the city of New York, your relator was arrested by divers persons claiming to be acting by authority of the government of the United States, and was by said persons conveyed to the United States immigration station at Ellis island, in the harbor of New York, and is now there imprisoned by the commissioner of immigration of the port of New York.

Complex systems are dynamic and may show high levels of variability in both space and time. It is often difficult to decide on what constitutes a given complex system, i.e., where system boundaries should be set, and what amounts to substantial change within the system. We discuss two central themes: the nature of system definitions and their ability to cope with change, and the importance of system definitions for the mental metamodels that we use to describe and order ideas about (...) system change. Systems can only be considered as single study units if they retain their identity. Previous system definitions have largely ignored the need for both spatial and temporal continuity as essential attributes of identity. After considering the philosophical issues surrounding identity and system definitions, we examine their application to modeling studies. We outline a set of five alternative metamodels that capture a range of the basic dynamics of complex systems. Although Holling’s adaptive cycle is a compelling and widely applicable metamodel that fits many complex systems, there are systems that do not necessarily follow the adaptive cycle. We propose that more careful consideration of system definitions and alternative metamodels for complex systems will lead to greater conceptual clarity in the field and, ultimately, to more rigorous research. (shrink)

Unification in description logics has been proposed as a novel inference service that can, for example, be used to detect redundancies in ontologies. The inexpressive description logic EL is of particular interest in this context since, on the one hand, several large biomedical ontologies are defined using EL. On the other hand, unification in EL has been shown to be NP-complete and, thus, of considerably lower complexity than unification in other description logics of similarly restricted expressive power. However, EL (...) allows the use of the top concept, which represents the whole interpretation domain, whereas the large medical ontology SNOMED CT makes no use of this feature. Surprisingly, removing the top concept from EL makes the unification problem considerably harder. More precisely, we will show that unification in EL without the top concept is PSPACE-complete. In addition to the decision problem, we also consider the problem of actually computing EL−⊤-unifiers. (shrink)

The SRL of King is a sound, complete and decidable logic designed specifically to support formalisms for the HPSG of Pollard and Sag. The SRL notion of modellability in a signature is particularly important for HPSG, and the present paper modifies an elegant method due to Blackburn and Spaan in order to prove that – modellability in each computable signature is 1 0 – modellability in some finite signature is 1 0 -hard, and – modellability in some finite signature is (...) decidable. (shrink)

In this paper, missing attribute values in incomplete data sets have three possible interpretations: lost values, attribute-concept values and ‘do not care’ conditions. For rule induction, we use characteristic sets and generalized maximal consistent blocks. Therefore, we apply six different approaches for data mining. As follows from our previous experiments, where we used an error rate evaluated by ten-fold cross validation as the main criterion of quality, no approach is universally the best. Thus, we decided to compare our six approaches (...) using complexity of rule sets induced from incomplete data sets. We show that the smallest rule sets are induced from incomplete data sets with attribute-concept values, while the most complicated rule sets are induced from data sets with lost values. The choice between interpretations of missing attribute values is more important than the choice between characteristic sets and generalized maximal consistent blocks. (shrink)

This book stands at the intersection of two topics: the decidability and computational complexity of hybrid logics, and the deductive systems designed for them. Hybrid logics are here divided into two groups: standard hybrid logics involving nominals as expressions of a separate sort, and non-standard hybrid logics, which do not involve nominals but whose expressive power matches the expressive power of binder-free standard hybrid logics.The original results of this book are split into two parts. This division reflects the (...) division of the book itself. The first type of results concern model-theoretic and complexity properties of hybrid logics. Since hybrid logics which we call standard are quite well investigated, the efforts focused on hybrid logics referred to as non-standard in this book. Non-standard hybrid logics are understood as modal logics with global counting operators ) whose expressive power matches the expressive power of binder-free standard hybrid logics. The relevant results comprise: 1. Establishing a sound and complete axiomatization for the modal logic K with global counting operators ), which can be easily extended onto other frame classes, 2. Establishing tight complexity bounds, namely NExpTime-completeness for the modal logic with global counting operators defined over the classes of arbitrary, reflexive, symmetric, serial and transitive frames ), MT), MD), MB), MK4) with numerical subscripts coded in binary. Establishing the exponential-size model property for this logic defined over the classes of Euclidean and equivalential frames ), MS5).Results of the second type consist of designing concrete deductive systems for standard and non-standard hybrid logics. More precisely, they include: 1. Devising a prefixed and an internalized tableau calculi which are sound, complete and terminating for a rich class of binder-free standard hybrid logics. An interesting feature of indicated calculi is the nonbranching character of the rule, 2. Devising a prefixed and an internalized tableau calculi which are sound, complete and terminating for non-standard hybrid logics. The internalization technique applied to a tableau calculus for the modal logic with global counting operators is novel in the literature, 3. Devising the first hybrid algorithm involving an inequality solver for modal logics with global counting operators. Transferring the arithmetical part of reasoning to an inequality solver turned out to be sufficient in ensuring termination.The book is directed to philosophers and logicians working with modal and hybrid logics, as well as to computer scientists interested in deductive systems and decision procedures for logics. Extensive fragments of the first part of the book can also serve as an introduction to hybrid logics for wider audience interested in logic.The content of the book is situated in the areas of formal logic and theoretical computer science with some elements of the theory of computational complexity. (shrink)

We consider the problem of recognizing important properties of logical calculi and find complexity bounds for some decidable properties. For a given logical system L, a property P of logical calculi is called decidable over L if there is an algorithm which for any finite set Ax of new axiom schemes decides whether the calculus L + Ax has the property P or not. In [11] the complexity of tabularity, pre-tabularity, and interpolation problems over the intuitionistic logic Int (...) and over modal logic S4 was studied, also we found the complexity of amalgamation problems in varieties of Heyting algebras and closure algebras. In the present paper we deal with positive calculi. We prove NP-completeness of tabularity, DP-hardness of pretabularity and PSPACE-completeness of interpolation problem over Int + . In addition to above-mentioned properties, we consider Beth's definability properties. Also we improve some complexity bounds for properties of superintuitionistic calculi. (shrink)

The interpretability logic ILP is the interpretability logic of all sufficiently strong |$\varSigma _1$|-sound finitely axiomatised theories, such as the Gödel-Bernays set theory. The interpretability logic IL is a strict subset of the intersection of the interpretability logics of all so-called reasonable theories, IL(All). It is known that both ILP and ILW are decidable, however their complexity has not been resolved previously. In [10] it was shown that the basic interpretability logic IL is PSPACE-complete. Here we prove the same (...) for ILP and ILW. (shrink)

We propose two alternatives to Xu’s axiomatization of Chellas’s STIT. The first one simplifies its presentation, and also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of Chellas’s STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal operators (...) is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and Chellas’s STIT. (shrink)

We analyzed the patients’ perception of prenatal diagnosis of fetal cardiac pathology, and the reasons for choosing to continue with pregnancy despite being eligible to receive a medical termination of pregnancy. We also identified the challenges, the motives interfering in decision-making, and the consequences of the decisions on pregnancy, child and mother. This descriptive, prospective and longitudinal study was conducted in France, amongst pregnant women who wished to continue their pregnancy despite an unfavorable medical advice. Socio-demographic data were collected through (...) a questionnaire. Such questionnaire covered information assessing the parents/mother’s perception of prenatal diagnosis, and medical termination of pregnancy, their interpretation of the established diagnosis and their motives for not considering pregnancy termination. 72 eligible patients were analyzed over one year: mean age 33 ± 6.89 years, 47 patients had already given birth to ≥1 healthy child. Mean gestational age at the detection of fetal cardiac pathologies was 30 ± 4.37 weeks of amenorrhea. Patients decided to keep the child after 3 ± 1.25 consultations. 56 patients made their decision with their husbands and 16 made their decision alone. Reasons for declining the medical termination were culpability and responsibility, ideologies and convictions, mistrust and hope. Newborns of 67 patients died with a mean survival duration of 38 days. Patient informed consent should be sought before any decision in neonatology, even if conflicting with the medical team’s knowledge and the pregnant mother’s benefits. Decisions to accept or decline pregnancy termination depend on the patients’ psychological character, ideologies, convictions, and mistrust in the diagnosis/prognosis, or hope in the fetus survival. (shrink)

This paper presents proofs of completeness and decidability of a non-temporal fragment of an Xstit logic. This shows a distinction between the non-temporal fragments of Xstit logic and regular stit logic since the latter is undecidable. The proof of decidability is via the finite model property. The finite model property is shown to hold by constructing a filtration. However, the set that is used to filter the models isn’t simply closed under subformulas, it has more complex closure conditions. (...) The filtration set is akin to the Fischer–Ladner closure of a set used to show completeness and decidability of propositional dynamic logic. (shrink)

Many of the benefits and burdens we might experience in our lives — from bank loans to bail terms — are increasingly decided by institutions relying on algorithms. In a sense, this is nothing new: algorithms — instructions whose steps can, in principle, be mechanically executed to solve a decision problem — are at least as old as allocative social institutions themselves. Algorithms, after all, help decision-makers to navigate the complexity and variation of whatever domains they are designed for. (...) In another sense, however, this development is startlingly new: not only are algorithms being deployed in ever more social contexts, they are being mechanically executed not merely in principle, but pervasively in practice. Due to recent advances in computing technology, the benefits and burdens we experience in our lives are now increasingly decided by automata, rather than each other. How are we to morally assess these technologies? In this chapter, I propose a preliminary conceptual schema for identifying and locating the various injustices of automated, algorithmic social decision systems, from a broadly liberal perspective. (shrink)

We investigate the computational complexity of deciding whether a given inference rule is admissible for some modal and superintuitionistic logics. We state a broad condition under which the admissibility problem is coNEXP-hard. We also show that admissibility in several well-known systems (including GL, S4, and IPC) is in coNE, thus obtaining a sharp complexity estimate for admissibility in these systems.

In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.

BackgroundEverybody has the right to decide whether to receive specific medical treatment or not and to provide their free, prior and informed consent to do so. As dementia progresses, people with Alzheimer’s dementia (PwAD) can lose their capacity to provide informed consent to complex medical treatment. When the capacity to consent is lost, the autonomy of the affected person can only be guaranteed when an interpretable and valid advance directive exists. Advance directives are not yet common in Germany, and their (...) validity is often questionable. Once the dementia diagnosis has been made, it is assumed to be too late to write an advance directive. One approach used to support the completion of advance directives is ‘Respecting Choices’®—an internationally recognised, evidence-based model of Advance Care Planning (ACP), which, until now, has not been evaluated for the target group of PwAD. This study’s aims include (a) to investigate the proportion of valid advance directives in a memory clinic population of persons with suspected AD, (b) to determine the predictors of valid advance directives, and (c) to examine whether the offer of ACP can increase the proportion of valid advance directives in PwAD.MethodWe intend to recruit at leastN = 250 participants from two memory clinics in 50 consecutive weeks. Of these, the first 25 weeks constitute the baseline phase (no offer of ACP), the following 25 weeks constitute the intervention phase (offer of ACP). The existence and validity of an advance directive will be assessed twice (before and after the memory clinic appointment). Moreover, potential predictors of valid advance directives are assessed.DiscussionThe results of this study will enhance the development of consent procedures for advance directives of PwAD based on the ACP/Respecting Choices (R) approach. Therefore, this project contributes towards increasing the autonomy and inclusion of PwAD and the widespread acceptance of valid advance directives in PwAD.Trial RegistrationDRKS, DRKS00026691, registered 15th of October 2021,https://www.drks.de/drks_web/navigate.do?navigationId=trial.HTML&TRIAL_ID=DRKS00026691. (shrink)

In this paper, we consider the role of conversations in contributing to healthcare quality improvement. More specifically, we suggest that conversations can be important in responding to what we call ’normative complexity’. As well as reflecting on the value of conversations, the aim is to introduce the dimension of normative complexity as something that requires theoretical and practical attention alongside the more recognised challenges of complex systems, which we label, for short, as ’explanatory complexity’. In brief, normative (...) complexity relates to the inherent difficulty of deciding what kinds of changes are ’improvements’ or, more broadly, what is valuable in healthcare. We suggest that explanatory and normative complexity intersect and that anyone interested in healthcare improvement needs to be sensitive to both. After briefly introducing the idea of normative complexity, we consider some contrasting examples of conversations, reflecting on how they do and might contribute to healthcare quality. We discuss both conversations that are deliberately organised and facilitated (’orchestrated conversations’) and more informally occurring and routine conversations. In the first half of the paper, we draw on some examples of orchestrated and routine conversations to open up these issues. In the second half of the paper, we bring some more theoretical lenses to bear on both conversations and normative complexity, summarise what we take to be the value of conversations and draw together some of the implications of our discussion. In summary, we argue that conversations can play a crucial role in negotiating the normative complexity of healthcare quality improvement because of their capacity to hold together a plurality of perspectives, to contribute and respond to emergence and to help underpin institutional conditions for empathy and imagination. (shrink)

In his paper, ‘Patients, doctors and risk attitudes’, Makins argues that doctors, when choosing a treatment for their patient, need to follow their risk profile.1 He presents a pair of fictitious diseases facing a patient who either has ‘exemplitis’, which requires no treatment or ‘caseopathy’, which is severe and disabling and for which there is a treatment with unpleasant side effects. The doctor needs to decide whether the patient should pursue the unpleasant treatment, just in case he has caseopathy. Makins (...) believes that rational-choice theory is a productive way to approach this problem. This theory frames all decisions as gambles. Each possible gamble (eg, not to pursue treatment) leads, probabilistically, to a set of outcomes (life with no disease and no side effects, but also, possibly, life with a disabling disease, since no treatment is taken). Utilities of these outcomes and probabilities that they will happen are combined to yield a number—expected utility. One is supposed to gamble—to make a choice—in a way that maximises this expected utility. Makins takes this framework for granted and is focused on an additional complication, the patient’s risk preference. He believes that, in his hypothetical example, even if expected utility were exactly the same, withholding treatment …. (shrink)

The class $$\mathsf{TPA}$$ TPA of t rue p airing a lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of $$\mathsf{TPA}$$ TPA nor the first order theory of $$\mathsf{TPA}$$ TPA are decidable. Moreover, we show that the set of all equations valid in $$\mathsf{TPA}$$ TPA is exactly on the $$\Pi ^1_1$$ Π 1 1 level. We consider the class $$\mathsf{TPA}^-$$ (...) TPA - of the relation algebra reducts of $$\mathsf{TPA}$$ TPA ’s, as well. We prove that the equational theory of $$\mathsf{TPA}^-$$ TPA - is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work. (shrink)

Expressiveness and decidability are two core aspects of programming languages that should be thoroughly known by those who use them; this includes knowledge of their metalanguages a.k.a. formal grammars. The van Wijngaarden grammars (WGs) are capable of generating all the languages in the Chomsky hierarchy and beyond; this makes them a relevant tool in the design of (more) expressive programming languages. But this expressiveness comes at a very high cost: The syntax of WGs is extremely complex and the decision (...) problem for the generated languages is generally unsolvable. With this in mind, I provide here a short primer of the syntax of WGs, which includes syntactic restrictions that guarantee decidability for the corresponding generated languages. (shrink)

There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for (...) entanglement, in: R.S. Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

We study the extension of public announcement logic PAL by public assignments, which we call PALA. Just as in the case of PAL, the standard procedure for deciding PALA validity, i.e. the use of so-called reduction axioms to translate PALA formulae into formulae in epistemic logic EL, may lead to exponential growth. In this paper, we show that such a price is not mandatory, for we provide a polynomial translation of PALA into EL. This is based on abbreviations of subformulae (...) by new propositional letters. Such optimal translation also enables us to show the computational complexity of the problem of deciding PALA validity, which turns out to be coNP-complete in the single-agent case and PSPACE-complete in the multiagent case. (shrink)

Who gets to decide what it means to live a healthy lifestyle, and how important a healthy lifestyle is to a good life? As more governments make preventing obesity and diet-related illness a priority, it has become more important to consider the ethics and acceptability of their efforts. When it comes to laws and policies that promote healthy eating—such as special taxes on sugary drinks or programs to encourage consumption of fruits and vegetables—critics argue that these policies are paternalistic, and (...) that they limit individual autonomy over food choices. In our book Healthy Eating Policy and Political Philosophy: A Public Reason Approach (Barnhill and Bonotti 2022), we argue that both paternalistic justifications for healthy eating efforts and anti-paternalistic arguments against them can be grounded in perfectionist views that overly prioritize some values over others. We therefore propose a more inclusive, public reason approach to healthy eating policy that will be appealing to those who take pluralism and cultural diversity seriously, by providing a framework through which different kinds of values, including but not limited to autonomy and health, can be factored into the public justification for healthy eating efforts. Additionally, the book adopts a ‘farm to fork’ approach to the ethics of healthy eating efforts: it engages with theories and debates in political philosophy, considers the implications of different theoretical positions for healthy eating efforts, and then develops a framework for assessing policies that can be used by researchers and policymakers. As well as offering a novel normative analysis of healthy eating policy, we also provide a theoretical framework that will be applicable beyond healthy eating policy to a wide range of public policy scenarios. We are extremely grateful to the contributors to this symposium for their thoughtful commentaries on our book. In this article, we provide a critical reflection on the issues they raise with regard to some key aspects of our analysis. (shrink)

While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic ( $\mathcal{PAL }$ ) with distributed knowledge, in particular their expressivity, axiomatisations and complexity. $\mathcal{PAL }$ extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on $\mathcal{PACD }$ , the result of adding both common (...) and distributed knowledge to $\mathcal{PAL }$ , which is more expressive than each of its component logics. We introduce an axiomatisation of $\mathcal{PACD }$ , which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with $S5$ knowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show that $\mathcal{PACD }$ is decidable, more precisely that it is $\textsc {exptime}$ -complete. This result also carries over to $\mathcal{S 5\mathcal CD }$ with common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs. (shrink)

In R [on the application of SG and others (previously JS and others)] v Secretary of State for Work and Pensions, the United Kingdom Supreme Court evaluated the legality of the benefit cap. The Court was sharply divided but decided by a narrow margin that the benefit cap did not amount to a violation of the claimants’ human rights. While the majority accepted that the gender discrimination was justified, the Court noted that the current measures fell short of the United (...) Kingdom’s responsibilities under the United Nations Convention on the Rights of the Child. This could prove of the outmost importance as the government elected in May 2015 has announced further reductions to the existing benefit cap. The case comment evaluates whether the Court paid enough attention to the multifaceted nature of poverty and discrimination, and argues that the impact the benefit cap has had specifically on women from black and ethnic minorities should have been considered. (shrink)