Extended algorithmic logic (EAL) as introduced in [18] is a modified version of extended +-valued algorithmic logic. Only two-valued predicates and two-valued propositional variables occur in EAL. The role of the +-valued logic is restricted to construct control systems (stacks) of pushdown algorithms whereas their actions are described by means of the two-valued logic. Thus EAL formalizes a programming theory with recursive procedures but without the instruction CASE.The aim of this paper is to discuss (...) EAL and prove the completeness theorem. A complete formalization of EAL was announced in [20] but no proof of the completeness theorem was given. (shrink)

ABSTRACT To more efficiently cover a wide spectrum of conceptual modeling applications such as computer-aided design, computer-aided manufacturing, and medical information systems, we envision multi-paradigm design environments which have reasoning capability to support analyzing specifcations for correctness. For such applications, information system designers employ conceptual models characterized by semantically-rich specification languages. The problem of providing a comprehensive formal framework for such languages has not been adequately addressed. This paper investigates a formal system for this purpose called Event-Formula Logic (EFL). (...) The analysis focuses in particular on characterizing correctness of database updates. Its applicability is demonstrated from two perspectives: deriving preconditions that guarantee a given update will not violate an integrity constraint, and determining alternative integrity maintenance rules for performing corrective actions when the application semantics requires this update interpretation. The work described in this paper represents an important step in the analysis of database update semantics through the use of algorithmic logic. As a result, it contributes towards providing a formal basis for semantically-rich information system design environments. (shrink)

We develop a functional abstraction principle for the type-free algorithmic logic introduced in our earlier work. Our approach is based on the standard combinators but is supplemented by the novel use of evaluation trees. Then we show that the abstraction principle leads to a Curry fixed point, a statement C that asserts C ⇒ A where A is any given statement. When A is false, such a C yields a paradoxical situation. As discussed in our earlier work, this (...) situation leaves one no choice but to restrict the use of a certain class of implicational rules including modus ponens. (shrink)

There is significant interest in type-free systems that allow flexible self-application. Such systems are of interest in property theory, natural language semantics, the theory of truth, theoretical computer science, the theory of classes, and category theory. While there are a variety of proposed type-free systems, there is a particularly natural type-free system that we believe is prototypical: the logic of recursive algorithms. Algorithmic logic is the study of basic statements concerning algorithms and the algorithmic rules of (...) inference between such statements. As shown in [1], the threat of paradoxes, such as the Curry paradox, requires care in implementing rules of inference in this context. As in any type-free logic, some traditional rules will fail. The first part of the paper develops a rich collection of inference rules that do not lead to paradox. The second part identifies traditional rules of logic that are paradoxical in algorithmic logic, and so should be viewed with suspicion in type-free logic generally. (shrink)

This note presents a point of view upon the notions of programsubstitution which are the tools for proving properties of programs of algorithmic logics [5], [3] being sufficiently strong and universal to comprise almost all previously introduced theories of programming, and the so-called extended algorithmic logic [1], [2] and algorithmic logic with nondeterministic programs [4]. It appears that the mentioned substitution rule allows us to examine more deeply algorithmic properties of terms, formulas and programs. (...) Besides the problem of Post-completeness and structural completeness of algorithmic logics strengthened additionally by the rule of substitution is raised. (shrink)

Spatial and diagrammatic reasoning is a significant part not only of logical abilities, but also of logical studies. The authors of this paper consider some novel trends in studying this type of reasoning. They show that there are the following two main trends in spatial logic: (i) logical studies of the distribution of various objects in space (logic of geometry, logic of colors, etc.); (ii) logical studies of the space algorithms applied by nature itself (logic of (...) swarms, logic of fungi colonies, etc.). (shrink)

In the present paper, we develop the algorithmic correspondence theory for hybrid logic with binder |$\mathcal {H}(@, \downarrow )$|⁠. We define the class of Sahlqvist inequalities for |$\mathcal {H}(@, \downarrow )$|⁠, and each inequality of which is shown to have a first-order frame correspondent effectively computable by an algorithm |$\textsf {ALBA}^{\downarrow }$|⁠.

Algorithmic chemistries are often based on a fixed formalism which limits the fragment of chemistry expressible in the domain of the models. This results in limited applicability of the models in contemporary mathematical chemistry and is due to the poor fit between the logic used for model construction and the system being modeled. In this paper, I propose a system-oriented methodology which selects a formalism through a mapping of chemical transformation rules to proof-theoretic structural rules. Using a formal (...) specification framework from the field of artificial chemistry, expressive adequacy is ensured by the choice of logic being based on the system properties to be modeled. To illustrate the methodology, a case study is provided that shows how the proposed approach selects linear logic for modeling resource sensitivity and the proof-theoretic interpretation facilitates translation to a programming language. Since the method results in a plurality of models, I conclude with a discussion on how the proposal contributes to multi-model paradigms in computational pharmacology. (shrink)

The previously introduced algorithm \sqema\ computes first-order frame equivalents for modal formulae and also proves their canonicity. Here we extend \sqema\ with an additional rule based on a recursive version of Ackermann's lemma, which enables the algorithm to compute local frame equivalents of modal formulae in the extension of first-order logic with monadic least fixed-points \mffo. This computation operates by transforming input formulae into locally frame equivalent ones in the pure fragment of the hybrid mu-calculus. In particular, we prove (...) that the recursive extension of \sqema\ succeeds on the class of `recursive formulae'. We also show that a certain version of this algorithm guarantees the canonicity of the formulae on which it succeeds. (shrink)

An algebraic approach to programs called recursive coroutines — due to Janicki [3] — is based on the idea to consider certain complex algorithms as algebraics models of those programs. Complex algorithms are generalizations of pushdown algorithms being algebraic models of recursive procedures (see Mazurkiewicz [4]). LCA — logic of complex algorithms — was formulated in [11]. It formalizes algorithmic properties of a class of deterministic programs called here complex recursive ones or interacting stacks-programs, for which complex algorithms (...) constitute mathematical models. LCA is in a sense an extension of algorithmic logic as initiated by Salwicki [14] and of extended algorithmic logic EAL as formulated and examined by the present author in [8], [9], [10]. In LCA — similarly as in EAL-ω + -valued logic is applied as a tool to construct control systems (stacks) occurring in corresponding algorithms. The aim of this paper is to give a complete axiomatization. of LCA and to prove a completeness theorem. (shrink)

Proceedings of the Steklov Institute of Mathematics is a cover-to-cover translation of the Trudy Matematicheskogo Instituta imeni V.A. Steklova of the Russian Academy of Sciences. Each issue ordinarily contains either one book-length article or a collection of articles pertaining to the same topic.

In a previous work we introduced the algorithm \SQEMA\ for computing first-order equivalents and proving canonicity of modal formulae, and thus established a very general correspondence and canonical completeness result. \SQEMA\ is based on transformation rules, the most important of which employs a modal version of a result by Ackermann that enables elimination of an existentially quantified predicate variable in a formula, provided a certain negative polarity condition on that variable is satisfied. In this paper we develop several extensions of (...) \SQEMA\ where that syntactic condition is replaced by a semantic one, viz. downward monotonicity. For the first, and most general, extension \SSQEMA\ we prove correctness for a large class of modal formulae containing an extension of the Sahlqvist formulae, defined by replacing polarity with monotonicity. By employing a special modal version of Lyndon's monotonicity theorem and imposing additional requirements on the Ackermann rule we obtain restricted versions of \SSQEMA\ which guarantee canonicity, too. (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)

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)

The present paper is devoted to computational aspects of propositional inconsistency-adaptive logics. In particular, we prove (relativized versions of) some principal results on computational complexity of derivability in such logics, namely in cases of CLuN r and CLuN m , i.e., CLuN supplied with the reliability strategy and the minimal abnormality strategy, respectively.

In this work we develop goal-directed deduction methods for the implicational fragment of several modal logics. We give sound and complete procedures for strict implication of K, T, K4, S4, K5, K45, KB, KTB, S5, G and for some intuitionistic variants. In order to achieve a uniform and concise presentation, we first develop our methods in the framework of Labelled Deductive Systems [Gabbay 96]. The proof systems we present are strongly analytical and satisfy a basic property of cut admissibility. We (...) then show that for most of the systems under consideration the labelling mechanism can be avoided by choosing an appropriate way of structuring theories. One peculiar feature of our proof systems is the use of restart rules which allow to re-ask the original goal of a deduction. In case of K, K4, S4 and G, we can eliminate such a rule, without loosing completeness. In all the other cases, by dropping such a rule, we get an intuitionistic variant of each system. The present results are part of a larger project of a goal directed proof theory for non-classical logics; the purpose of this project is to show that most implicational logics stem from slight variations of a unique deduction method, and from different ways of structuring theories. Moreover, the proof systems we present follow the logic programming style of deduction and seem promising for proof search [Gabbay and Reyle 84, Miller et al. 91]. (shrink)

This volume presents the proceedings from the Eleventh Brazilian Logic Conference on Mathematical Logic held by the Brazilian Logic Society in Salvador, Bahia, Brazil. The conference and the volume are dedicated to the memory of professor Mario Tourasse Teixeira, an educator and researcher who contributed to the formation of several generations of Brazilian logicians. Contributions were made from leading Brazilian logicians and their Latin-American and European colleagues. All papers were selected by a careful refereeing processs and were (...) revised and updated by their authors for publication in this volume. There are three sections: Advances in Logic, Advances in Theoretical Computer Science, and Advances in Philosophical Logic. Well-known specialists present original research on several aspects of model theory, proof theory, algebraic logic, category theory, connections between logic and computer science, and topics of philosophical logic of current interest. Topics interweave proof-theoretical, semantical, foundational, and philosophical aspects with algorithmic and algebraic views, offering lively high-level research results. (shrink)

We apply and extend the theory and methods of algorithmic correspondence theory for modal logics, developed over the past 20 years, to the language LR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {L}_R$$\end{document} of relevance logics with respect to their standard Routley–Meyer relational semantics. We develop the non-deterministic algorithmic procedure PEARL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PEARL}$$\end{document} for computing first-order equivalents of formulae of the language LR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} (...) \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {L}_R$$\end{document}, in terms of that semantics. PEARL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PEARL}$$\end{document} is an adaptation of the previously developed algorithmic procedures SQEMA and ALBA. We then identify a large syntactically defined class of inductive formulae in LR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {L}_R$$\end{document}, analogous to previously defined such classes in the classical, distributive and non-distributive modal logic settings, and show that PEARL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PEARL}$$\end{document} succeeds for every inductive formula and correctly computes a first-order definable condition which is equivalent to it with respect to frame validity. We also provide a detailed comparison with two earlier works, each extending the class of Sahlqvist formulae to relevance logics, and show that both are subsumed by simple subclasses of inductive formulae. (shrink)

The formulas-as-types isomorphism tells us that every proof and theorem, in the intuitionistic implicational logic $H_\rightarrow$, corresponds to a lambda term or combinator and its type. The algorithms of Bunder very efficiently find a lambda term inhabitant, if any, of any given type of $H_\rightarrow$ and of many of its subsystems. In most cases the search procedure has a simple bound based roughly on the length of the formula involved. Computer implementations of some of these procedures were done in (...) Dekker. In this paper we extend these methods to full classical propositional logic as well as to its various subsystems. This extension has partly been implemented by Oostdijk. (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).

Within the program of finding axiomatizations for various parts of computability logic, it was proven earlier that the logic of interactive Turing reduction is exactly the implicative fragment of Heyting’s intuitionistic calculus. That sort of reduction permits unlimited reusage of the computational resource represented by the antecedent. An at least equally basic and natural sort of algorithmic reduction, however, is the one that does not allow such reusage. The present article shows that turning the logic of (...) the first sort of reduction into the logic of the second sort of reduction takes nothing more than just deleting the contraction rule from its Gentzen-style axiomatization. The first sort of interactive reduction is also shown to come in three natural versions. While those three versions are very different from each other, their logical behaviors turn out to be indistinguishable, with that common behavior being precisely captured by implicative intuitionistic logic. Among the other contributions of the present article is an informal introduction of a series of new — finite and bounded — versions of recurrence operations and the associated reduction operations. (shrink)

This article is both a comment on Neyland’s ‘On organizing algorithms’ and a supplementary note to our ‘The concept of algorithm as an interpretative key of modern rationality’. In the first part we discuss the concepts of algorithm and recursive function from a different perspective from that of our previous article. Our cultural reference for these concepts is once again computability theory. We give additional arguments in support of the idea that a culture informed by an algorithmic logic (...) has promoted modern rationality both in science and in society. We stress again the importance of distinguishing between algorithms applied to quantifiable entities such as space, time and value and those applied to ontological entities such as human actions. In the second case, the algorithm is applied outside its domain of definition and leads to social disaggregation. (shrink)

In this paper, I develop an algorithmic impossible-worlds model of belief and knowledge that provides a middle ground between models that entail that everyone is logically omniscient and those that are compatible with even the most egregious kinds of logical incompetence. In outline, the model entails that an agent believes (knows) φ just in case she can easily (and correctly) compute that φ is true and thus has the capacity to make her actions depend on whether φ. The model (...) thereby captures the standard view that belief and knowledge ground are constitutively connected to dispositions to act. As I explain, the model improves upon standard algorithmic models developed by Parikh, Halpern, Moses, Vardi, and Duc, among other ways, by integrating them into an impossible-worlds framework. The model also avoids some important disadvantages of recent candidate middle-ground models based on dynamic epistemic logic or step logic, and it can subsume their most important advantages. (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)

A concise yet rigorous introduction to logic and discrete mathematics. This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade. The chapters on logic - propositional and first-order - provide a robust toolkit for logical reasoning, emphasizing the conceptual understanding of the language and the (...) semantics of classical logic as well as practical applications through the easy to understand and use deductive systems of Semantic Tableaux and Resolution. The chapters on set theory, number theory, combinatorics and graph theory combine the necessary minimum of theory with numerous examples and selected applications. Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in the accompanying solutions manual. Key Features: Suitable for a variety of courses for students in both Mathematics and Computer Science. Extensive, in-depth coverage of classical logic, combined with a solid exposition of a selection of the most important fields of discrete mathematics Concise, clear and uncluttered presentation with numerous examples. Covers some applications including cryptographic systems, discrete probability and network algorithms. Logic and Discrete Mathematics: A Concise Introduction is aimed mainly at undergraduate courses for students in mathematics and computer science, but the book will also be a valuable resource for graduate modules and for self-study. (shrink)

This paper explores how political theory may help us map algorithmic logics against different visions of the political. Drawing on Chantal Mouffe’s theories of agonistic pluralism, this paper depicts algorithms in public life in ten distinct scenes, in order to ask the question, what kinds of politics do they instantiate? Algorithms are working within highly contested online spaces of public discourse, such as YouTube and Facebook, where incompatible perspectives coexist. Yet algorithms are designed to produce clear “winners” from information (...) contests, often with little visibility or accountability for how those contests are designed. In isolation, many of these algorithms seem the opposite of agonistic: much of the complexity of search, ranking, and recommendation algorithms is nonnegotiable and kept far from view, inside an algorithmic “black box.” But what if we widen our perspective? This paper suggests agonistic pluralism as both a design ideal for engineers and a provocation to understand algorithms in a broader social context: rather than focusing on the calculations in isolation, we need to account for the spaces of contestation where they operate. (shrink)

In this paper we examine two approaches to the formal treatment of the notion of problem in the paradigm of algorithmic semantics. Namely, we will explore an approach based on Martin-Löf’s Constructive Type Theory, which can be seen as a direct continuation of Kolmogorov’s original calculus of problems, and an approach utilizing Tichý’s Transparent Intensional Logic, which can be viewed as a non-constructive attempt of interpreting Kolmogorov’s logic of problems. In the last section we propose Kolmogorov and (...) CTT-inspired modifications to TIL-based approach. The focus will be on non-empirical problems only. (shrink)

Often machine learning programs inherit social patterns reflected in their training data without any directed effort by programmers to include such biases. Computer scientists call this algorithmic bias. This paper explores the relationship between machine bias and human cognitive bias. In it, I argue similarities between algorithmic and cognitive biases indicate a disconcerting sense in which sources of bias emerge out of seemingly innocuous patterns of information processing. The emergent nature of this bias obscures the existence of the (...) bias itself, making it difficult to identify, mitigate, or evaluate using standard resources in epistemology and ethics. I demonstrate these points in the case of mitigation techniques by presenting what I call ‘the Proxy Problem’. One reason biases resist revision is that they rely on proxy attributes, seemingly innocuous attributes that correlate with socially-sensitive attributes, serving as proxies for the socially-sensitive attributes themselves. I argue that in both human and algorithmic domains, this problem presents a common dilemma for mitigation: attempts to discourage reliance on proxy attributes risk a tradeoff with judgement accuracy. This problem, I contend, admits of no purely algorithmic solution. (shrink)