Computer Science - Logic in Computer Science Publications (50)


Computer Science - Logic in Computer Science Publications

Logic programming is the computer programming paradigm where a subset of first order logic, known as definite clause logic, is used as a general purpose programming language. A logic program is a finite set of sentences written in definite clause logic, defining relations among objects. A logic program interpreter, taking a program, answers queries about relations defined in the program, using some particular logical inference rule, such as SLD resolution, which is a special case of resolution rule restricted to definite clauses. Read More

The categorical compositional approach to meaning has been successfully applied in natural language processing, outperforming other models in mainstream empirical language processing tasks. We show how this approach can be generalized to conceptual space models of cognition. In order to do this, first we introduce the category of convex relations as a new setting for categorical compositional semantics, emphasizing the convex structure important to conceptual space applications. Read More

Calculi of string diagrams are increasingly used to present the syntax and algebraic structure of various families of circuits, including signal flow graphs, electrical circuits and quantum processes. In many such approaches, the semantic interpretation for diagrams is given in terms of relations or corelations (generalised equivalence relations) of some kind. In this paper we show how semantic categories of both relations and corelations can be characterised as colimits of simpler categories. Read More

We propose a new formulation of Quantum Turing Ma- chines, as an extension of those proposed by Bernstein and Vazirani. For this new class of Quantum Turing Machines, both finite and infinite computations are meaningful -an infinite computation does not correspond trivially to a divergent function. Moreover, we propose a natural observation protocol for the new QTMs, that does not modify the probability of the possible outcomes of the machines. Read More

We present a weakest-precondition-style calculus for reasoning about the expected values (pre-expectations) of \emph{mixed-sign unbounded} random variables after execution of a probabilistic program. The semantics of a while-loop is well-defined as the limit of iteratively applying a functional to a zero-element just as in the traditional weakest pre-expectation calculus, even though a standard least fixed point argument is not applicable in this context. A striking feature of our semantics is that it is always well-defined, even if the expected values do not exist. Read More

For an endofunctor $H$ on a hyper-extensive category preserving countable coproducts we describe the free corecursive algebra on $Y$ as the coproduct of the final coalgebra for $H$ and the free $H$-algebra on $Y$. As a consequence, we derive that $H$ is a cia functor, i.e. Read More

Multiphase ranking functions ($\mathit{M{\Phi}RFs}$) were proposed as a means to prove the termination of a loop in which the computation progresses through a number of "phases", and the progress of each phase is described by a different linear ranking function. Our work provides new insights regarding such functions for loops described by a conjunction of linear constraints (single-path loops). We provide a complete polynomial-time solution to the problem of existence and of synthesis of $\mathit{M{\Phi}RF}$ of bounded depth (number of phases), when variables range over rational or real numbers; a complete solution for the (harder) case that variables are integer, with a matching lower-bound proof, showing that the problem is coNP-complete; and a new theorem which bounds the number of iterations for loops with $\mathit{M{\Phi}RFs}$. Read More

This paper considers the permissive supervisor synthesis for probabilistic systems modeled as Markov Decision Processes (MDP). Such systems are prevalent in power grids, transportation networks, communication networks and robotics. Unlike centralized planning and optimization based planning, we propose a novel supervisor synthesis framework based on learning and compositional model checking to generate permissive local supervisors in a distributed manner. Read More

Yoshida demonstrated how to eliminate the bound names coming from the input prefix in the asynchronous pi calculus, but her combinators still depend on the "new" operator to bind names. We modify Yoshida's combinators by replacing "new" and replication with reflective operators to provide the first combinator calculus with no bound names into which the asynchronous pi calculus has a faithful embedding. We also show that multisorted Lawvere theories enriched over graphs suffice to capture the operational semantics of the calculus. Read More

Statecharts are frequently used as a modeling formalism in the design of state-based systems. Formal verification techniques are also often applied to prove certain properties about the behavior of the system. One of the most efficient techniques for formal verification is Counterexample-Guided Abstraction Refinement (CEGAR), which reduces the complexity of systems by automatically building and refining abstractions. Read More

Existing logical models do not fairly represent epistemic situations with fallible justifications, e.g., Russell's Prime Minister example, though such scenarios have long been at the center of epistemic studies. Read More

In process algebras such as ACP, parallel processes are considered to be interleaved in an arbitrary way. In the case of multi-threading as found in contemporary programming languages, parallel processes are actually interleaved according to some interleaving strategy. Interleaving strategies are also known as process-scheduling policies. Read More

Cell injection is a technique in the domain of biological cell micro-manipulation for the delivery of small volumes of samples into the suspended or adherent cells. It has been widely applied in various areas, such as gene injection, in-vitro fertilization (IVF), intracytoplasmic sperm injection (ISCI) and drug development. However, the existing manual and semi-automated cell injection systems require lengthy training and suffer from high probability of contamination and low success rate. Read More

We present a term rewrite system that formally models the Message Authenticator Algorithm (MAA), which was one of the first cryptographic functions for computing a Message Authentication Code and was adopted, between 1987 and 2001, in international standards (ISO 8730 and ISO 8731-2) to ensure the authenticity and integrity of banking transactions. Our term rewrite system is large (13 sorts, 18 constructors, 644 non-constructors, and 684 rewrite rules), confluent, and terminating. Implementations in thirteen different languages have been automatically derived from this model and used to validate 200 official test vectors for the MAA. Read More

This paper considers on a network routing protocol known as Better Approach to Mobile Ad hoc Networks (B.A.T. Read More

We present a formal model for a fragmentation and a reassembly protocol running on top of the standardised CAN bus, which is widely used in automotive and aerospace applications. Although the CAN bus comes with an in-built mechanism for prioritisation, we argue that this is not sufficient and provide another protocol to overcome this shortcoming. Read More

The Stream Control Transmission Protocol (SCTP) is a Transport Layer protocol that has been proposed as an alternative to the Transmission Control Protocol (TCP) for the Internet of Things (IoT). SCTP, with its four-way handshake mechanism, claims to protect the Server from a Denial-of-Service (DoS) attack by ensuring the legitimacy of the Client, which has been a known issue pertaining to the three-way handshake of TCP. This paper compares the handshakes of TCP and SCTP to discuss its shortcomings and strengths. Read More

We identify multirole logic as a new form of logic in which conjunction/disjunction is interpreted as an ultrafilter on the power set of some underlying set (of roles) and the notion of negation is generalized to endomorphisms on this underlying set. We formalize both multirole logic (MRL) and linear multirole logic (LMRL) as natural generalizations of classical logic (CL) and classical linear logic (CLL), respectively, and also present a filter-based interpretation for intuitionism in multirole logic. Among various meta-properties established for MRL and LMRL, we obtain one named multiparty cut-elimination stating that every cut involving one or more sequents (as a generalization of a (binary) cut involving exactly two sequents) can be eliminated, thus extending the celebrated result of cut-elimination by Gentzen. Read More

We present two fully mechanized proofs of Dilworths and Mirskys theorems in the Coq proof assistant. Dilworths Theorem states that in any finite partially ordered set (poset), the size of a smallest chain cover and a largest antichain are the same. Mirskys Theorem is a dual of Dilworths Theorem. Read More

Under a reversible semantics, computation steps can be undone. This paper addresses the integration of reversible semantics into process languages for communication-centric systems, equipped with behavioral types. In prior work, we introduced a monitors-as-memories approach to seamlessly integrate reversible semantics into a process model in which concurrency is governed by session types (a class of behavioral types), covering binary (two-party) protocols with synchronous communications. Read More

Suppose we have been sold on the idea that formalised proofs in an LCF system should resemble their written counterparts, and so consist of formulas that only provide signposts for a fully verified proof. To be practical, most of the fully elaborated verification must then be done by way of general purpose proof procedures. Now if these are the only procedures we implement outside the kernel of logical rules, what does the theorem prover look like? We give our account, working from scratch in the ProofPeer theorem prover, making observations about this new setting along the way. Read More

We introduce a new methodology based on refinement for testing the functional correctness of hardware and low-level software. Our methodology overcomes several major drawbacks of the de facto testing methodologies used in industry: (1) it is difficult to determine completeness of the properties and tests under consideration (2) defining oracles for tests is expensive and error-prone (3) properties are defined in terms of low-level designs. Our approach compiles a formal refinement conjecture into a runtime check that is performed during simulation. Read More

We contribute a general apparatus for dependent tactic-based proof refinement in the LCF tradition, in which the statements of subgoals may express a dependency on the proofs of other subgoals; this form of dependency is extremely useful and can serve as an algorithmic alternative to extensions of LCF based on non-local instantiation of schematic variables. Additionally, we introduce a novel behavioral distinction between refinement rules and tactics based on naturality. Our framework, called Dependent LCF, is already deployed in the nascent RedPRL proof assistant for computational cubical type theory. Read More

Negotiations are a formalism for describing multiparty distributed cooperation. Alternatively, they can be seen as a model of concurrency with synchronized choice as communication primitive. Well-designed negotiations must be sound, meaning that, whatever its current state, the negotiation can still be completed. Read More


With state-based methods, checking that an implementation satisfies a higher-level specification requires describing how the higher-level concepts in the specification are represented by the lower-level data structures of the implementation. This approach was first proposed in the domain of sequential systems by Hoare in 1972. Hoare called the description an abstraction function. Read More

The following problem is shown undecidable: given regular languages L,K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczy\'nski from LICS 2016. Read More

This volume contains the proceedings of MARS 2017, the second workshop on Models for Formal Analysis of Real Systems, held on April 29, 2017 in Uppala, Sweden, as an affiliated workshop of ETAPS 2017, the European Joint Conferences on Theory and Practice of Software. The workshop emphasises modelling over verification. It aims at discussing the lessons learned from making formal methods for the verification and analysis of realistic systems. Read More

A decade ago, Abdulla et al introduced the elegant concept of decisiveness for denumerable Markov chains [1]. Roughly decisiveness allows one to lift most good properties from finite Markov chains to denumerable ones, and therefore to adapt existing verification algorithms to infinite-state models. Denumerable Markov chains however do not encompass stochastic real-time systems, and general stochastic transition systems (STSs) are needed. Read More

Higher-order recursion schemes (HORS) have received much attention as a useful abstraction of higher-order functional programs with a number of new verification techniques employing HORS model-checking as their centrepiece. We give an account of the C-SHORe tool, which contributed to the ongoing quest for a truly scalable model-checker for HORS by offering a different, automata theoretic perspective. C-SHORe implements the first practical model-checking algorithm that acts on a generalisation of pushdown automata equi-expressive with HORS called collapsible pushdown systems (CPDS). Read More

Population protocols are a well established model of computation by anonymous, identical finite state agents. A protocol is well-specified if from every initial configuration, all fair executions reach a common consensus. The central verification question for population protocols is the well-specification problem: deciding if a given protocol is well-specified. Read More

We propose a definition of computable manifold by introducing computability as a structure that we impose to a given topological manifold, just in the same way as differentiability or piecewise linearity are defined for smooth and PL manifolds respectively. Using the framework of computable topology and Type-2 theory of effectivity, we develop computable versions of all the basic concepts needed to define manifolds, like computable atlases and (computably) compatible computable atlases. We prove that given a computable atlas $\Phi$ defined on a set $M$, we can construct a computable topological space $(M, \tau_\Phi, \beta_\Phi, \nu_\Phi)$, where $\tau_\Phi$ is the topology on $M$ induced by $\Phi$ and that the equivalence class of this computable space characterizes the computable structure determined by $\Phi$. Read More

We develop first-order logic and some extensions for incomplete information scenarios and consider related complexity issues. Read More

We propose a way of reasoning about minimal and maximal values of the weights of transitions in a weighted transition system (WTS). This perspective induces a notion of bisimulation that is coarser than the classic bisimulation: it relates states that exhibit transitions to bisimulation classes with the weights within the same boundaries. We propose a customized modal logic that expresses these numeric boundaries for transition weights by means of particular modalities. Read More

Communicating transactions is a form of distributed, non-isolated transactions which provides a simple construct for building concurrent systems. In this paper we develop a logical framework to express properties of the observable behaviour of such systems. This comprises three nominal modal logics which share standard communication modalities but have distinct past and future modalities involving transactional commits. Read More

Given a $\Pi^{\mu}_2$ formula of the modal $\mu$ calculus, it is decidable whether it is equivalent to a $\Sigma^{\mu}_2$ formula. Read More

We propose a new linear algebraic approach to the computation of Tarskian semantics in logic. We embed a finite model M in first-order logic with N entities in N-dimensional Euclidean space R^N by mapping entities of M to N dimensional one-hot vectors and k-ary relations to order-k adjacency tensors (multi-way arrays). Second given a logical formula F in prenex normal form, we compile F into a set Sigma_F of algebraic formulas in multi-linear algebra with a nonlinear operation. Read More

We define and study the Functional Aggregate Query (FAQ) problem, which captures common computational tasks across a very wide range of domains including relational databases, logic, matrix and tensor computation, probabilistic graphical models, constraint satisfaction, and signal processing. Simply put, an FAQ is a declarative way of defining a new function from a database of input functions. We present "InsideOut", a dynamic programming algorithm, to evaluate an FAQ. Read More

The monadic shallow linear Horn fragment is well-known to be decidable and has many application, e.g., in security protocol analysis, tree automata, or abstraction refinement. Read More

In our implementation of geometric resolution, the most costly operation is subsumption testing (or matching): One has to decide for a three-valued, geometric formula, if this formula is false in a given interpretation. The formula contains only atoms with variables, equality, and existential quantifiers. The interpretation contains only atoms with constants. Read More

We extend the notion of localic completion of generalised metric spaces by Steven Vickers to the setting of generalised uniform spaces. A generalised uniform space (gus) is a set X equipped with a family of generalised metrics on X, where a generalised metric on X is a map from the product of X to the upper reals satisfying zero self-distance law and triangle inequality. For a symmetric generalised uniform space, the localic completion lifts its generalised uniform structure to a point-free generalised uniform structure. Read More

Bi-Intuitionistic Stable Tense Logics (BIST Logics) are tense logics with a Kripke semantics where worlds in a frame are equipped with a pre-order as well as with an accessibility relation which is 'stable' with respect to this pre-order. BIST logics are extensions of a logic, BiSKt, which arose in the semantic context of hypergraphs, since a special case of the pre-order can represent the incidence structure of a hypergraph. In this paper we provide, for the first time, a Hilbert-style axiomatisation of BISKt and prove the strong completeness of BiSKt. Read More

Affiliations: 1Sun Yat-Sen University, 2Tallinn University of Technology

The syntax of modal graphs is defined in terms of the continuous cut and broken cut following Charles Peirce's notation in the gamma part of his graphical logic of existential graphs. Graphical calculi for normal modal logics are developed based on a reformulation of the graphical calculus for classical propositional logic. These graphical calculi are of the nature of deep inference. Read More

Affiliations: 1Albert-Ludwigs-Universität Freiburg, 2Technical University of Denmark, 3Albert-Ludwigs-Universität Freiburg, 4Albert-Ludwigs-Universität Freiburg

Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Recently, Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. We extend the DEL-based epistemic planning framework to include perspective shifts, allowing us to define new notions of sequential and conditional planning with implicit coordination. Read More

Affiliations: 1Zühlke Engineering AG, 2School of Mathematics, Institute for Research in Fundamental Sciences, 3University of Bern

Justification logics are modal-like logics with the additional capability of recording the reason, or justification, for modalities in syntactic structures, called justification terms. Justification logics can be seen as explicit counterparts to modal logics. The behavior and interaction of agents in distributed system is often modeled using logics of knowledge and time. Read More

Over the past two decades several fragments of first-order logic have been identified and shown to have good computational and algorithmic properties, to a great extent as a result of appropriately describing the image of the standard translation of modal logic to first-order logic. This applies most notably to the guarded fragment, where quantifiers are appropriately relativized by atoms, and the fragment defined by restricting the number of variables to two. The aim of this talk is to review recent work concerning these fragments and their popular extensions. Read More

Affiliations: 1The Institute of Mathematical Sciences, Chennai, 2Tata Institute of Fundamental Research, Mumbai

In temporal logics, a central question is about the choice of modalities and their relative expressive power, in comparison to the complexity of decision problems such as satisfiability. In this tutorial, we will illustrate the study of such questions over finite word models, first with logics for Unambiguous Starfree Regular Languages (UL), originally defined by Schutzenberger, and then for extensions with constraints, which appear in interval logics. We present Deterministic temporal logics, with diverse sets of modalities, which also characterize UL. Read More

Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we aim to give an accessible introduction to DEL-based epistemic planning. Read More

${\rm CTT}_{\rm qe}$ is a version of Church's type theory with global quotation and evaluation operators that is engineered to reason about the interplay of syntax and semantics and to formalize syntax-based mathematical algorithms. ${\rm CTT}_{\rm uqe}$ is a variant of ${\rm CTT}_{\rm qe}$ that admits undefined expressions, partial functions, and multiple base types of individuals. It is better suited than ${\rm CTT}_{\rm qe}$ as a logic for building networks of theories connected by theory morphisms. Read More

This article presents a new game semantics for Martin-L\"of type theory (MLTT), in which each game is equipped with selected isomorphism strategies that represent (computational) proofs for (intensional) equality between strategies on the game. These isomorphism strategies interpret propositional equalities in MLTT. As a main result, we have obtained a first game semantics for MLTT that refutes the principle of uniqueness of identity proofs (UIP) and validates univalence axiom (UA) though it does not model non-trivial higher equalities. Read More