Scholars of critical algorithmic studies, including those from geography, anthropology, Science and Technology Studies and communication studies, have begun to consider how algorithmic devices and platforms facilitate democratic practices. In this article, I draw on a comparative ethnography of two alternative open-source algorithmic platforms – Decide Madrid and vTaiwan – to consider how they are dynamically constituted by differing algorithmic–human relationships. I compare how different algorithmic–human relationships empower citizens to influence political decision-making through proposing, commenting, (...) and voting on the urban issues that should receive political resources in Taipei and Madrid. I argue that algorithmic empowerment is an emerging process in which algorithmic–human relationships orient away from limitations and towards conditions of plurality, actionality, and power decentralisation. This argument frames algorithmic empowerment as bringing about empowering conditions that allow (underrepresented) individuals to shape policy-making and consider plural perspectives for political change and action, not as an outcome-driven, binary assessment (i.e. yes/no). This article contributes a novel, situated, and comparative conceptualisation of algorithmic empowerment that moves beyond technological determinism and universalism. (shrink)

We consider one aspect of the problem of specification and verification of reactive real-time systems which involve operations and constraints concerning time. Time is continuous what is motivated by specifications of hybrid systems. Our goal is to try to find a framework that is based on applied first order logic that permits to represent the verification problem directly, completely and conservatively , and that is apt to describe interesting decidable classes, maybe showing way to feasible algorithms. To achieve this goal (...) we use a first order timed logic that is an extension of a decidable theory of reals with timed functions. This logic permits, on the one hand, to rewrite directly and completely requirements and, on the other hand, to describe executions of various timed algorithms—here we consider block Gurevich abstract state machines because of their theoretical clarity and sufficient expressive power. Then we describe one decidable class of the verification problem that is based on notions reflecting finiteness properties of systems of control. These notions may be of independent interest, as, in particular, they give a way to describe a limited usage of arithmetics preserving decidability that is not covered by existing model-theoretic approaches. As an example we consider the generalized railroad crossing problem that we analyze in its entirety. (shrink)

The paper studies the logic TL(NBox+-wC) – logic of discrete linear time with current time point clusters. Its language uses modalities Diamond+ (possible in future) and Diamond- (possible in past) and special temporal operations, – Box+w (weakly necessary in future) and Box-w (weakly necessary in past). We proceed by developing an algorithm recognizing theorems of TL(NBox+-wC), so we prove that TL(NBox+-wC) is decidable. The algorithm is based on reduction of formulas to inference rules and converting the rules in special reduced (...) normal form, and, then, on checking validity of such rules in models of singleexponential size in the rules. Also we consider the admissibility problem for TL(NBox+-wC) and show how to reduce the problem for admissibility to the decidability of TL(NBox+-wC) itself using definable universal modalities. (shrink)

In information societies, operations, decisions and choices previously left to humans are increasingly delegated to algorithms, which may advise, if not decide, about how data should be interpreted and what actions should be taken as a result. More and more often, algorithms mediate social processes, business transactions, governmental decisions, and how we perceive, understand, and interact among ourselves and with the environment. Gaps between the design and operation of algorithms and our understanding of their ethical implications can have severe consequences (...) affecting individuals as well as groups and whole societies. This paper makes three contributions to clarify the ethical importance of algorithmic mediation. It provides a prescriptive map to organise the debate. It reviews the current discussion of ethical aspects of algorithms. And it assesses the available literature in order to identify areas requiring further work to develop the ethics of algorithms. (shrink)

The problem of algorithmic structuring of proofs in the sequent calculi LK and LKB ( LK where blocks of quantifiers can be introduced in one step) is investigated, where a distinction is made between linear proofs and proofs in tree form. In this framework, structuring coincides with the introduction of cuts into a proof. The algorithmic solvability of this problem can be reduced to the question of k-l-compressibility: "Given a proof of length k , and l ≤ k (...) : Is there is a proof of length ≤ l ?" When restricted to proofs with universal or existential cuts, this problem is shown to be (1) undecidable for linear or tree-like LK-proofs (corresponds to the undecidability of second order unification), (2) undecidable for linear LKB-proofs (corresponds to the undecidability of semi-unification), and (3) decidable for tree-like LKB -proofs (corresponds to a decidable subprob- lem of semi-unification). (shrink)

We prove that if an n-element algebra generates the variety \ which is actively structurally complete, then the cardinality of the carrier of each subdirectly irreducible algebra in \ is at most \\cdot n^{2\cdot n}}\). As a consequence, with the use of known results, we show that there exist algorithms deciding whether a given finite algebra \ generates the structurally complete variety \\) in the cases when \\) is congruence modular or \\) is congruence meet-semidistributive or \ is a semigroup.

Self-driving cars hold out the promise of being safer than manually driven cars. Yet they cannot be a 100 % safe. Collisions are sometimes unavoidable. So self-driving cars need to be programmed for how they should respond to scenarios where collisions are highly likely or unavoidable. The accident-scenarios self-driving cars might face have recently been likened to the key examples and dilemmas associated with the trolley problem. In this article, we critically examine this tempting analogy. We identify three important ways (...) in which the ethics of accident-algorithms for self-driving cars and the philosophy of the trolley problem differ from each other. These concern: the basic decision-making situation faced by those who decide how self-driving cars should be programmed to deal with accidents; moral and legal responsibility; and decision-making in the face of risks and uncertainty. In discussing these three areas of disanalogy, we isolate and identify a number of basic issues and complexities that arise within the ethics of the programming of self-driving cars. (shrink)

Introduction -- Algorithms, programs, procedures, and abstract automata -- Functioning of algorithms and automata, computation, and operations with algorithms and automata -- Basic postulates and axioms for algorithms -- Power of algorithms and classes of algorithms: comparison and evaluation -- Computing, accepting, and deciding modes of algorithms and programs -- Problems that people solve and related properties of algorithms -- Boundaries for algorithms and computation -- Software and hardware verification and testing -- Conclusion.

We introduce a reciprocity criterion for coalition formation among goal-directed agents, which we call the indecomposable do-ut-des property. It refines an older reciprocity property, called the do-ut-des or give-to-get property by considering the fact that agents prefer to form coalitions whose components cannot be formed independently. A formal description of this property is provided as well as an analysis of algorithms and their complexity. We provide an algorithm to decide whether a coalition has the desired property, and we show that (...) the problem to verify whether a single coalition satisfies the property is tractable. Moreover, we provide an algorithm to search all the sub-coalitions of a given coalition satisfying the new property. Even if this problem is not computationally tractable, we show that in several cases, also the complexity of this problem may decrease considerably. (shrink)

The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability (...) and definability theory. Here we give a unified presentation, including some new results, of how to use the Feferman–Vaught Theorem, and some new variations thereof, algorithmically in the case of Monadic Second Order Logic MSOL . We then extend the technique to graph polynomials where the range of the summation of the monomials is definable in MSOL . Here the Feferman–Vaught Theorem for these polynomials generalizes well known splitting theorems for graph polynomials. Again, these can be used algorithmically. Finally, we discuss extensions of MSOL for which the Feferman–Vaught Theorem holds as well. (shrink)

From 1929 through 1944, Wittgenstein endeavors to clarify mathematical meaningfulness by showing how (algorithmically decidable) mathematical propositions, which lack contingent "sense," have mathematical sense in contrast to all infinitistic "mathematical" expressions. In the middle period (1929-34), Wittgenstein adopts strong formalism and argues that mathematical calculi are formal inventions in which meaningfulness and "truth" are entirely intrasystemic and epistemological affairs. In his later period (1937-44), Wittgenstein resolves the conflict between his intermediate strong formalism and his criticism of set theory by requiring (...) that a mathematical calculus (vs. a "sign-game") must have an extrasystemic, real world application, thereby returning to the weak formalism of the Tractatus. (shrink)

The debate on the right to be forgotten on Google involves the relationship between human information processing and digital processing by algorithms. The specificity of digital memory is not so much its often discussed inability to forget. What distinguishes digital memory is, instead, its ability to process information without understanding. Algorithms only work with data without remembering or forgetting. Merely calculating, algorithms manage to produce significant results not because they operate in an intelligent way, but because they “parasitically” exploit the (...) intelligence, the memory, and the attribution of meaning by human actors. The specificity of algorithmic processing makes it possible to bypass the paradox of remembering to forget, which up to now blocked any human-based forgetting technique. If you decide to forget some memory, the most immediate effect is drawing attention to it, thereby activating remembering. Working differently from human intelligence, however, algorithms can implement, for the first time, the classical insight that it might be possible to reinforce forgetting not by erasing memories but by multiplying them. After discussing several projects on the web which implicitly adopt this approach, the article concludes by raising some deeper problems posed when algorithms use data and metadata to produce information that cannot be attributed to any human being. (shrink)

The problem of algorithms is, I think, also the question of the framework by which we determine the validity of our knowledge. The frames built with the help of algorithms are strong, unambiguous and legible. This causes that algorithmic sciences are called, in colloquial language, ‘exact’ and the knowledge constructed in this way is referred to as ‘specific’. Not everyone is thinking about the fact that algorithms provide certain knowledge, but only if we meet certain restrictive conditions, we will (...) build new, additional kind of framework. According to Odo Marquard, this will be the case if we decide to dominate exclusive reason. This reason, i.e. the rejecting, bypassing and reducing reason, will bypass and disregard all the limitations that algorithmic knowledge carries, sometimes emphasizing the extremely arrogant basic advantage of algorithmic knowledge, i.e. its certainty. (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)

Machine learning classifiers are increasingly used to inform, or even make, decisions significantly affecting human lives. Fairness concerns have spawned a number of contributions aimed at both identifying and addressing unfairness in algorithmic decision-making. This paper critically discusses the adoption of group-parity criteria (e.g., demographic parity, equality of opportunity, treatment equality) as fairness standards. To this end, we evaluate the use of machine learning methods relative to different steps of the decision-making process: assigning a predictive score, linking a classification (...) to the score, and adopting decisions based on the classification. Throughout our inquiry we use the COMPAS system, complemented by a radical simplification of it (our SAPMOC I and SAPMOC II models), as our running examples. Through these examples, we show how a system that is equally accurate for different groups may fail to comply with group-parity standards, owing to different base rates in the population. We discuss the general properties of the statistics determining the satisfaction of group-parity criteria and levels of accuracy. Using the distinction between scoring, classifying, and deciding, we argue that equalisation of classifications/decisions between groups can be achieved thorough group-dependent thresholding. We discuss contexts in which this approach may be meaningful and useful in pursuing policy objectives. We claim that the implementation of group-parity standards should be left to competent human decision-makers, under appropriate scrutiny, since it involves discretionary value-based political choices. Accordingly, predictive systems should be designed in such a way that relevant policy goals can be transparently implemented. Our paper presents three main contributions: (1) it addresses a complex predictive system through the lens of simplified toy models; (2) it argues for selective policy interventions on the different steps of automated decision-making; (3) it points to the limited significance of statistical notions of fairness to achieve social goals. (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)

In classical propositional logic, a theory T is prime iff it is complete. In Łukasiewicz infinite-valued logic the two notions split, completeness being stronger than primeness. Using toric desingularization algorithms and the fine structure of prime ideal spaces of free ℓ -groups, in this paper we shall characterize prime theories in infinite-valued logic. We will show that recursively enumerable prime theories over a finite number of variables are decidable, and we will exhibit an example of an undecidable r.e. prime theory (...) over countably many variables. (shrink)

Given any collection F of computable functions over the reals, we show that there exists an algorithm that, given any sentence A containing only bounded quantifiers and functions in F, and any positive rational number delta, decides either “A is true”, or “a delta-strengthening of A is false”. Moreover, if F can be computed in complexity class C, then under mild assumptions, this “delta-decision problem” for bounded Sigma k-sentences resides in Sigma k. The results stand in sharp contrast to the (...) well-known undecidability of the general first-order theories with these functions, and serve as a theoretical basis for the use of numerical methods in decision procedures for formulas over the reals. (shrink)

Description logics are a family of knowledge representation formalisms that are descended from semantic networks and frames via the system Kl-one. During the last decade, it has been shown that the important reasoning problems (like subsumption and satisfiability) in a great variety of description logics can be decided using tableau-like algorithms. This is not very surprising since description logics have turned out to be closely related to propositional modal logics and logics of programs (such as propositional dynamic logic), for which (...) tableau procedures have been quite successful.Nevertheless, due to different underlying institutions and applications, most description logics differ significantly from run-of-the-mill modal and program logics. Consequently, the research on tableau algorithms in description logics led to new techniques and results, which are, however, also of interest for modal logicians. In this article, we will focus on three features that play an important rôle in description logics (number restrictions, terminological axioms, and role constructors), and show how they can be taken into account by tableau algorithms. (shrink)

We present a characterization of confluence for term rewriting systems, which is then refined for special classes of rewriting systems. The refined characterization is used to obtain a polynomial time algorithm for deciding the confluence of ground term rewrite systems. The same approach also shows the decidability of confluence for shallow and linear term rewriting systems. The decision procedure has a polynomial time complexity under the assumption that the maximum arity of a function symbol in the signature is a (...) constant. (shrink)

The paper deals with a temporal multi-agent logic TMAZ, which imitates taking of decisions based on agents' access to knowledge by their interaction. The interaction is modelled by possible communication channels between agents in special temporal Kripke/hintikka-like models. The logic TMAZ distinguishes local and global decisions-making. TMAZ is based on temporal Kripke/hintikka models with agents' accessibility relations defined on states of all possible time clusters C(i) (where indexes i range over all integer numbers Z). The main result provides a decision (...) algorithm for TMAZ (so, we prove that TMAZ is decidable). This algorithm also solves the satisfiability problem. In the final part of the paper, we consider the admissibility problem for inference rules in TMAZ, and show that this problem is decidable for TMAZ as well. (shrink)

We say φ is an ∀∃ sentence if and only if φ is logically equivalent to a sentence of the form ∀ x∃ y ψ(x,y), where ψ(x,y) is a quantifier-free formula containing no variables except x and y. In this paper we show that there are algorithms to decide whether or not a given ∀∃ sentence is true in (1) an algebraic number field K, (2) a purely transcendental extension of an algebraic number field K, (3) every field with characteristic (...) 0, (4) every algebraic number field, (5) every cyclic (abelian, radical) extension field over Q, and (6) every field. (shrink)

Decisions are taken by humans very often during professional as well as leisure activities. It is particularly evident during surfing the Internet: selecting web sites to explore, choosing needed information in search engine results or deciding which product to buy in an on-line store. Recommender systems are electronic applications, the aim of which is to support humans in this decision making process. They are widely used in many applications: adaptive WWW servers, e-learning, music and video preferences, internet stores etc. In (...) on-line solutions, such as e-shops or libraries, the aim of recommendations is to show customers the products which they are probably interested in. As input data the following are taken: shopping basket archives, ratings of the products or servers log files.The article presents a solution of recommender system which helps users to select an interesting product. The system analyses data from other customers' ratings of the products. It uses clustering methods to find similarities among the users and proposed techniques to identify users' profiles. The system was implemented in Apache Mahout environment and tested on a movie database. Selected similarity measures are based on: Euclidean distance, cosine as well as correlation coefficient and loglikehood function. (shrink)

We use here the notions and results from algebraic theory of programs in order to give a new proof of the decidability theorem for Suszko logic SCI (Theorem 3).We generalize the method used in the proof of that theorem in order to prove a more general fact that any prepositional logic which admits a cut-free Gentzen type formalization is decidable (Theorem 6).

We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.

The combination of Fuzzy Logics and Description Logics has been investigated for at least two decades because such fuzzy DLs can be used to formalize imprecise concepts. In particular, tableau algorithms for crisp Description Logics have been extended to reason also with their fuzzy counterparts. It has turned out, however, that in the presence of general concept inclusion axioms this extension is less straightforward than thought. In fact, a number of tableau algorithms claimed to deal correctly with fuzzy DLs with (...) GCIs have recently been shown to be incorrect. In this paper, we concentrate on fuzzy \, the fuzzy extension of the well-known DL \. We present a terminating, sound, and complete tableau algorithm for fuzzy \ with arbitrary continuous t-norms. Unfortunately, in the presence of GCIs, this algorithm does not yield a decision procedure for consistency of fuzzy \ ontologies since it uses as a sub-procedure a solvability test for a finitely represented, but possibly infinite, system of inequations over the real interval [0,1], which are built using the t-norm. In general, it is not clear whether this solvability problem is decidable for such infinite systems of inequations. This may depend on the specific t-norm used. In fact, we also show in this paper that consistency of fuzzy \ ontologies with GCIs is undecidable for the product t-norm. This implies, of course, that for the infinite systems of inequations produced by the tableau algorithm for fuzzy \ with product t-norm, solvability is in general undecidable. We also give a brief overview of recently obtained decidability results for fuzzy \ w.r.t. other t-norms. (shrink)

In Homo Deus, Yuval Noah Harari argues that technological advances of the twenty-first century will usher in a significant shift in how humans make important life decisions. Instead of turning to the Bible or the Quran, to the heart or to our therapists, parents, and mentors, people will turn to Big Data recommendation algorithms to make these choices for them. Much as we rely on Spotify to recommend music to us, we will soon rely on algorithms to decide our careers, (...) spouses, and commitments. Harari also predicts that next, the state will take away individuals’ rights to make their own choices about their lives. If Google knows where your children would flourish best in school, why should the state allow a fallible human parent to decide? Liberalism—which, as Harari uses this term, refers to a state of society in which human freedom to choose is respected and championed—will collapse. In this paper, I argue that Harari’s conception of the future implications of recommendation algorithms is deeply flawed, for two reasons. First, users will not rely on algorithms to make decisions for them because they have no reason to trust algorithms, which are developed by companies with their own incentives, such as profit. Second, for most of our life decisions, algorithms will not be able to be developed, because the factors relevant to the decisions we face are unique to our situation. I present an alternative depiction of the future: instead of relying on algorithms to make decisions for us, humans will use algorithms to enhance our decision-making by helping us consider the most relevant choices first and notice information we might not otherwise. Finally, I will also argue that even if computers could make many of our decisions for us, liberalism as a political system would emerge unscathed. (shrink)

In this paper we prove, modulo Schanuel's Conjecture, that there are algorithms which decide if two exponential polynomials in π are equal in ℝ and if two exponential polynomials in π and i coincide in ℂ.

Much of the formal study of algorithmic concerns with respect to semantics for abstract argumentation frameworks has focused on the issue of computational complexity. In contrast matters regarding computability have been largely neglected. Recent trends in semantics have, however, started to concentrate not so much on the formulation of novel semantics but more on identifying common properties: for example, from basic ideas such as conflict-freeness through to quite sophisticated ideas such as serializability. The aim of this paper is to (...) look at the implications these more recent studies have for computability rather than computational complexity. (shrink)

Algorithmic systems are increasingly used by state agencies to inform decisions about humans. They produce scores on risks of recidivism in criminal justice, indicate the probability for a job seeker to find a job in the labor market, or calculate whether an applicant should get access to a certain university program. In this contribution, we take an interdisciplinary perspective, provide a bird’s eye view of the different key decisions that are to be taken when state actors decide to use (...) an algorithmic system, and illustrate these decisions with empirical examples from case studies. Building on these insights, we discuss the main pitfalls and promises of the use of algorithmic system by the state and focus on four levels: The most basic question whether an algorithmic system should be used at all, the regulation and governance of the system, issues of algorithm design, and, finally, questions related to the implementation of the system on the ground and the human–machine-interaction that comes with it. Based on our assessment of the advantages and challenges that arise at each of these levels, we propose a set of crucial questions to be asked when such intricate matters are addressed. (shrink)

Most jurisdictions require a patient to consent to any medical intervention. Clinicians ask a patient, ‘Given the pain and distress associated with our intervention and the predicted likelihood of this best-case outcome, do you want to accept the treatment?’ When a patient is incapable of deciding, clinicians may ask people who know the patient to say what the patient would decide; this is substituted judgement. In contrast, asking the same people to say how the person would make the decision is (...) substituted interests.1 The UK Mental Capacity Act 2005 uses the latter approach, and my comments appertain to that approach. When a patient lacks capacity, the question facing clinicians is, ‘Given the likely outcome of this treatment plan for the patient’s life in the long term, would the patient decide to accept the plan?’ This answer depends on the patient’s wishes, values and other factors they would use when deciding. The proposed development of an algorithm involves the following:2. (shrink)

We describe a decidable class of formulas in a first order timed logic that covers a good amount of properties of real-time distributed systems. Earlier we described a decidable class based on some finiteness properties, and sketched a decidable class in a weaker logic that captures periodicity properties, though without complete proof. The new feature of the decidable class presented here is to be able to treat parametric properties, in particular, properties that concern an arbitrary number of processes as compared (...) to the just mentioned class that could express only properties for a fixed, explicitly given number of processes. As before the properties may use non-trivial arithmetics. We also state another important feature of the class: if a verification formula is not true then our algorithm gives a quantifier-free description of all its counter-models of the complexity involved in the definition of the decidable class and that is quite representative. In conclusion we discuss theoretical and practical issues of the complexity and some open questions. (shrink)

ABSTRACT We show that there is a polynomial over the rational number field corresponding to each propositional formula in a given many-valued logic. To decide whether a propositional formula can be deduced from a finite set of such formulas (deduction problem), we only need to decide whether a polynomial vanishes on an algebraic variety. By using Wu's method, an algorithm for this problem is presented.

By PFM, we mean a finitely generated module over a principal ideal domain; a linear sentence is a sentence that contains no disjunctive and negative symbols. In this paper, we present an algorithm which decides the truth for linear sentences on a given PFM, and we discuss its time complexity. In particular, when the principal ideal domain is the ring of integers or a univariate polynomial ring over the field of rationals, the algorithm is polynomial-time. Finally, we consider some applications (...) to Abelian groups. (shrink)

The aim of this paper is to construct a tableau decision algorithm for the modal description logic K ALC with constant domains. More precisely, we present a tableau procedure that is capable of deciding, given an ALC-formula with extra modal operators (which are applied only to concepts and TBox axioms, but not to roles), whether is satisfiable in a model with constant domains and arbitrary accessibility relations. Tableau-based algorithms have been shown to be practical even for logics of rather high (...) complexity. This gives us grounds to believe that, although the satisfiability problem for K ALC is known to be NEXPTIME-complete, by providing a tableau decision algorithm we demonstrate that highly expressive description logics with modal operators have a chance to be implementable. The paper gives a solution to an open problem of Baader and Laux [5]. (shrink)

We prove that the observational equivalence of third-order finitary Idealized Algol is decidable using Game Semantics. By modelling the state explicitly in our games, we show that the denotation of a term M of this fragment of IA is a compactly innocent strategy-with-state, i.e. the strategy is generated by a finite view function fM. Given any such fM, we construct a real-time deterministic pushdown automaton that recognizes the complete plays of the knowing-strategy denotation of M. Since such plays characterize observational (...) equivalence, and there is an algorithm for deciding whether any two DPDAs recognize the same language, we obtain a procedure for deciding the observational equivalence of third-order finitary IA. Restricted to second-order terms, the DPDA representation cuts down to a deterministic finite automaton; thus our approach gives a new proof of Ghica and McCusker’s regular-expression characterization for this fragment. Our algorithmic representation of program meanings, which is compositional, provides a foundation for model-checking a wide range of behavioural properties of IA and other cognate programming languages. Another result concerns second-order IA with full recursion: we show that observational equivalence for this fragment is undecidable. (shrink)

This work provides proof-search algorithms and automated counter-model extraction for a class of STIT logics. With this, we answer an open problem concerning syntactic decision procedures and cut-free calculi for STIT logics. A new class of cut-free complete labelled sequent calculi G3LdmL^m_n, for multi-agent STIT with at most n-many choices, is introduced. We refine the calculi G3LdmL^m_n through the use of propagation rules and demonstrate the admissibility of their structural rules, resulting in auxiliary calculi Ldm^m_nL. In the single-agent case, we (...) show that the refined calculi Ldm^m_nL derive theorems within a restricted class of (forestlike) sequents, allowing us to provide proof-search algorithms that decide single-agent STIT logics. We prove that the proof-search algorithms are correct and terminate. (shrink)

The International Workshop on Combinatorial Algorithms was established in 1989 as the Australasian Workshop on Combinatorial Algorithms. As a consequence of the workshop's success in attracting mathematicians and computer scientists from around the world, it was decided at the 2006 meeting to go global, to change the workshop's name, and to hold it in appropriate venues around the world. The workshop supports basic research on the interface between mathematics and computing, specifically * Algorithms & Data Structures * Complexity Theory * (...) Algorithms on Graphs & Strings * Combinatorial Optimization * Cryptography & Information Security * Computational Biology * Communications Networks and many other related areas. This is Volume 1 in the series of IWOCA proceedings. See http: //www.iwoca.org/. (shrink)

Qualitative evidence concerning the relationship between QoL and a wide range of disabilities suggests that subjective judgments regarding other people’s QoL are wrong more often than not and that such judgments by medical practitioners in particular can be biased. Guided by their desire to do good and avoid harm, surgeons often rely on "the eyeball test" to decide whether a patient will or will not benefit from surgery. But the eyeball test can easily harbor a range of implicit judgments and (...) biases against patients with disabilities, including erroneous assumptions about QoL. We critique the use of the "eyeball" test and offer suggestions to reduce bias and ensure that patients’ values are more consistently prioritized in surgical decision-making. (shrink)

Perhaps nowhere better than, "On the Names of God," can readers discern Laclau's appreciation of theology, specifically, negative theology, and the radical potencies of political theology. // It is Laclau's close attention to Eckhart and Dionysius in this essay that reveals a core theological strategy to be learned by populist reasons or social logics and applied in politics or democracies to come. // This mode of algorithmically informed negative political theology is not mathematically inert. It aspires to relate a fraction (...) or ratio to a series ... It strains to reduce the decided determinateness of such seriality ever condemned to the naive metaphysics of bad infinity. // It is worth considering that it is the specific 'number' of Dionysius in differential identification with an ineffable god (and, as such, a singular becoming between theology and numbers) that is floating in at least two dimensions [of signification] (be it political Demand on the horizontal dimension or theological Desire on [a] floating dimension) that cannot but *perform the link that relinks* names of god with any political life, populist reason, social justice, or radical democracy straining toward peace. (shrink)

The motor modules during human walking are identified using non-negative matrix factorization from surface electromyography signals. The extraction of motor modules in healthy participants is affected by the change in pre-processing of EMG signals, such as low-pass filters ; however, the effect of different pre-processing methods, such as the number of necessary gait cycles in post-stroke patients with varying steps, remains unknown. We aimed to specify that the number of GCs influenced the motor modules extracted in the consideration of LPFs (...) in post-stroke patients. In total, 10 chronic post-stroke patients walked at a self-selected speed on an overground walkway, while EMG signals were recorded from the eight muscles of paretic lower limb. To verify the number of GCs, five GC conditions were set, namely, 25, 20, 15, 10, and 5 gate cycles with three LPFs. First, the number of modules, variability accounted for, and muscle weightings extracted by the NNMF algorithm were compared between the conditions. Next, a modified NNMF algorithm, in which the activation timing profiles among different GCs were unified, was performed to compare the muscle weightings more robustly between GCs. The number of motor modules was not significantly different, regardless of the GCs. The difference in VAF and muscle weightings in the different GCs decreased with the LPF of 4 Hz. Muscle weightings in 15 GCs or less were significantly different from those in 25 GCs using the modified NNMF. Therefore, we concluded that the variability extracted motor modules by different GCs was suppressed with lower LPFs; however, 20 GCs were needed for more representative extraction of motor modules during walking in post-stroke patients. (shrink)

Background: Current practice frequently fails to provide care consistent with the preferences of decisionally-incapacitated patients. It also imposes significant emotional burden on their surrogates. Algorithmic-based patient preference predictors (PPPs) have been proposed as a possible way to address these two concerns. While previous research found that patients strongly support the use of PPPs, the views of surrogates are unknown. The present study thus assessed the views of experienced surrogates regarding the possible use of PPPs as a means to help (...) make treatment decisions for decisionally-incapacitated patients. -/- Methods: This qualitative study used semi-structured interviews to determine the views of experienced surrogates [n=26] who were identified from two academic medical centers and two community hospitals. The primary outcomes were respondents’ overall level of support for the idea of using PPPs and the themes related to their views on how a PPP should be used, if at all, in practice. -/- Results: Overall, 21 participants supported the idea of using PPPs. The remaining five indicated that they would not use a PPP because they made decisions based on the patient’s best interests, not based on substituted judgment. Major themes which emerged were that surrogates, not the patient’s preferences, should determine how treatment decisions are made, and concern that PPPs might be used to deny expensive care or be biased against minority groups. -/- Conclusions: Surrogates, like patients, strongly support the idea of using PPPs to help make treatment decisions for decisionally-incapacitated patients. These findings provide support for developing a PPP and assessing it in practice. At the same time, patients and surrogates disagree over whose preferences should determine how treatment decisions are made, including whether to use a PPP. These findings reveal a fundamental disagreement regarding the guiding principles for surrogate decision-making. Future research is needed to assess this disagreement and consider ways to address it. (shrink)