Search

We propose a novel logic, called Frame Logic (FL), that extends first-order logic (with recursive definitions) using a construct Sp(.) that captures the implicit supports of formulas -- the precise subset of the universe upon which their meaning depends. Using such supports, we formulate proof rules that facilitate frame reasoning elegantly when the underlying model undergoes change. We show that the logic is expressive by capturing several data-structures and also exhibit a translation from a precise fragment of separation logic to frame logic. Finally, we design a program logic based on frame logic for reasoning with programs that dynamically update heaps that facilitates local specifications and frame reasoning. This program logic consists of both localized proof rules as well as rules that derive the weakest tightest preconditions in FL., This manuscript is an extended and revised version of the publication with the same title that appeared at ESOP 2022 (https://doi.org/10.1007/978-3-030-44914-8_19). It is currently under review

Priced timed automata (PTA) are discrete-event system models with temporal constraints and a cost function and are used to pose optimal scheduling and routing problems. To date, solutions to these problems have been found offline and executed open loop. \soutThe This open-loop control strategy makes it impossible to account for disturbances, i.e., changes in costs or scheduling constraints over time. To address this shortcoming, this work's first contribution is a closed-loop model predictive control (MPC) framework for PTA, enabling decision-making based on real-time model updates. To ensure the feasibility of an MPC problem, it is often desirable to soften constraints. However, the contemporary PTA theory does not consider soft constraints. Thus, this work's second contribution is to integrate constraint softening with PTA control by harnessing the capabilities of new solvers enabled by the recasting of the models and control problem into first-order logic by employing modified encoding schemes based on existing works. Finally, the proposed control framework and implementation are demonstrated in a simulation case study on the guidance of a product through a manufacturing system.

Propositional logic is the study of propositions, where a proposition is a statement that is either true or false. Propositionallogic may be used to encode simple arguments that are expressed in natural language, and to determine their validity. The validity of an argument may be determined from truth tables, or using the inference rules such as modus ponens to establish the conclusion via deductive steps. Predicate logic allows complex facts about the world to be represented, and new facts may be determined via deductive reasoning. Predicate calculus includes predicates, variables and quantifiers, and a predicate is a characteristic or property that the subject of a statement can have. The universal quantifier is used to express a statement such as that all members of the domain of discourse have property P, and the existential quantifier states that there is at least one value of x has property P.

This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games., 56 pages. Journal of Philosophical Logic (2021)

There are three main families of inference algorithms in first-order logic: direct inference and its application to deductive databases and production systems; backward inference procedures and logic programming systems; theorem proving systems based on the resolution method. When solving specific problems, the most effective algorithms are those that allow you to cover all the facts and axioms and must be taken into account in the process of inference. An example is considered in which it is necessary to prove the guilt of a person in murder. On the basis of statements, a knowledge base is formed from expressions, with the help of which an expression of first-order logic is compiled and proved using direct logical inference. The proof of the reasoning obtained in direct inference using the proof tree is given. However, direct inference provides for the implementation of all admissible stages of logical inference based on all known facts. The article also considers a method based on the resolution when implementing the reverse inference, taking into account the expression obtained in the direct inference. This expression is converted into a conjunctive normal formula using the laws of Boolean algebra and is proved by the elimination of events using the conjunction operation.

We present the concept of a theory machine, which is an atemporal computational formalism that is deployable within an arbitrary logical system. Theory machines are intended to capture computation on an arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device characterisable by a finite first-order theory machine is equivalent to that of a Turing machine. Whereas for infinite problems, their computational power is equivalent to that of a type-2 machine. We then develop a concept of complexity for theory machines, and prove that the class of problems decidable by a finite first order theory machine with polynomial resources is equal to 𝒩𝒫 ∩ co-𝒩𝒫.

U radu se ispituje mogućnost reprezentiranja Aristotelove rasprave o singularnoj predikaciji iz Kategorija 10, 13b27-35 u trima simboličkim idiomima – u jeziku logike prvog reda s identitetom, s i bez određenih opisa, te jezicima slobodnih logika – te se pokazuje zašto nijedna reprezentacija nije u potpunosti odgovarajuća. Prema prvoj opciji, obvezujemo Aristotela na (meta)logičke implikacije koje on ne prihvaća. Prema drugoj opciji, pripisujemo Aristotelu Russellovu teoriju imena. U konačnici, treća nas opcija ostavlja s pretpostavkom da se ‘postoji’ može reprezentirati predikatom. Takvu pretpostavku, međutim, Aristotel izričito odbija., The possibility of formal representation of Aristotle’s discussion about singular predication in Categories 10, 13b27-35 is investigated through three symbolic idioms: the first-order language with identity, with and without definitive description, and through the languages of free logics. I show that such representations are not fully adequate. According to the first option, we are committing Aristotle with some (meta)logical implications he is not willing to accept. According to the second option, we are burdening Aristotle with Russell’s theory of names. Finally, the third option leaves us with the assumption that ‘exist(s)’ could be represented with a predicate. This assumption, however, Aristotle emphatically rejects.

International audience; We present first-order (FO) and monadic second-order (MSO) logics with predicates 'between' and 'neighbour' that characterise the class of regular languages that are closed under the reverse operation and its subclasses. The ternary between predicate bet(x, y, z) is true if the position y is strictly between the positions x and z. The binary neighbour predicate N(x, y) is true when the the positions x and y are adjacent. It is shown that the class of reversible regular languages is precisely the class definable in the logics MSO(bet) and MSO(N). Moreover the class is definable by their existential fragments EMSO(bet) and EMSO(N), yielding a normal form for MSO formulas. In the first-order case, the logic FO(bet) corresponds precisely to the class of reversible languages definable in FO(

In this paper, we discourse an analysis of classical first-order predicate logic as a constraint satisfaction problem, CSP. First, we will offer our general framework for CSPs, and then apply it to first-order logic. We claim it would function as a new semantics, constraint semantics, for logic. Then, we prove the soundness and completeness theorems with respect to the constraint semantics. The latter theorem, which will be proven by a proof-search method, implies the cut-elimination theorem. Furthermore, using the constraint semantics, we make a new proof of the Craig interpolation theorem. Also, we will provide feasible algorithms to generate interpolants for some decidable fragments of first-order logic: the propositional logic and the monadic fragments. The algorithms, reflecting a ‘projection’ of an indexed relation, will show how to transform given formulas syntactically to obtain interpolants.

In this paper, we follow Gödel’s remarks on an envisioned theory of concepts to determine which properties should a logical basis of such a theory have. The discussion is organized around the question of suitability of the classical predicate calculus for this role. Some reasons to think that classical logic is not an appropriate basis for the theory of concepts, will be presented. We consider, based on these reasons, which alternative logical system could fare better as a logical foundation of, in Gödel’s opinion, the most important theory in logic yet to be developed. This paper should, in particular, motivate the study of partial predicates in a certain system of three-valued logic, as a promising starting point for the foundation of the theory of concepts.

By mimicking the standard definition for a formal language, we define what it is for a natural language to be compact. We set out a valid English argument none of whose finite subarguments is valid. We consider one by one objections to the argument's logical validity and then dismiss them. The conclusion is that English—and any other language with the capacity to express the argument—is not compact. This rules out a large class of logics as the correct foundational one, for example any sound and complete logic, and in particular first-order logic. The correct foundational logic is not compact.

Proofs are a key feature of modern propositional and first-order theorem provers. Proofs generated by such tools serve as explanations for unsatisfiability of statements. However, these explanations are complicated by proofs which are not necessarily as concise as possible. There are a wide variety of compression techniques for propositional resolution proofs but fewer compression techniques for first-order resolution proofs generated by automated theorem provers. This paper describes an approach to compressing first-order logic proofs based on lifting proof compression ideas used in propositional logic to first-order logic. The first approach lifted from propositional logic delays resolution with unit clauses, which are clauses that have a single literal. The second approach is partial regularization, which removes an inference $\eta $ when it is redundant in the sense that its pivot literal already occurs as the pivot of another inference in every path from $\eta $ to the root of the proof. This paper describes the generalization of the algorithms LowerUnits and RecyclePivotsWithIntersection (Fontaine et al.. Compression of propositional resolution proofs via partial regularization. In Automated Deduction—CADE-23—23rd International Conference on Automated Deduction, Wroclaw, Poland, July 31–August 5, 2011, p. 237--251. Springer, 2011) from propositional logic to first-order logic. The generalized algorithms compresses resolution proofs containing resolution and factoring inferences with unification. An empirical evaluation of these approaches is included.

We consider Hoare-style verification for the graph programming language GP 2. In previous work, graph properties were specified by so-called E-conditions which extend nested graph conditions. However, this type of assertions is not easy to comprehend by programmers that are used to formal specifications in standard first-order logic. In this paper, we present an approach to verify GP 2 programs with a standard first-order logic. We show how to construct a strongest liberal postcondition with respect to a rule schema and a precondition. We then extend this construction to obtain strongest liberal postconditions for arbitrary loop-free programs. Compared with previous work, this allows to reason about a vastly generalised class of graph programs. In particular, many programs with nested loops can be verified with the new calculus., Comment: In Proceedings GCM 2020, arXiv:2012.01181. arXiv admin note: substantial text overlap with arXiv:2010.14549

The Modal Predicate Calculus gives rise to issues surrounding the Barcan formulas, their converses, and necessary existence. I examine these issues by means of the Quantified Argument Calculus (Quarc), a recently developed, powerful formal logic system. Quarc is closer in syntax and logical properties to Natural Language than is the Predicate Calculus, a fact that lends additional interest to this examination, as Quarc might offer a better representation of our modal concepts. The validity of the Barcan formulas and their converses is shown by Quarc to be a result of the specific incorporation of quantification in the Predicate Calculus, and not as reflecting a feature of the interaction of quantification and modality more generally. Necessary existence is shown to follow from the identification, in the Predicate Calculus on its canonical interpretation, of particular quantification, ascription of existence and the ‘there is’ construction, three constructions which are distinguished in both Quarc and Natural Language. The issues surrounding the Barcan formulas, their converses and necessary existence are thus shown to be an artefact of a specific logic system, not an essential feature of our relevant modal concepts or of formal logic.

Cirquent calculus is a novel proof theory permitting component-sharing between logical expressions. Using it, the predecessor article ‘Elementary-base cirquent calculus I: Parallel and choice connectives’ built the sound and complete axiomatization $\textbf{CL16}$ of a propositional fragment of computability logic. The atoms of the language of $\textbf{CL16}$ represent elementary, i.e. moveless, games and the logical vocabulary consists of negation, parallel connectives and choice connectives. The present paper constructs the first-order version $\textbf{CL17}$ of $\textbf{CL16}$, also enjoying soundness and completeness. The language of $\textbf{CL17}$ augments that of $\textbf{CL16}$ by including choice quantifiers. Unlike classical predicate calculus, $\textbf{CL17}$ turns out to be decidable.

This study introduces a developed method to a smart computer-aided design/manufacturing (CAD/CAM) system, where layout design, process planning, and comprehensive computerized numerical control (CNC) code generation can be implemented to satisfy laser cutting holes, tapping, irregular and complicated profile processing, engraving, and burr back-scraping. The smart CAD/CAM(SCAM) system is developed as a commercial software product or application and firstly applied to flexible sheet metal machining center (BGL 130R). In this study, a formal modeling method involving Petri nets and first-order predicate logic is proposed to develop the smart manufacturing system. High-level Petri nets are employed to achieve the formal application architecture design of data flow for various functions, and the first-order logic used to represent the process plan is defined and deduced according to the machining methods. The developed system possesses the following characteristics: (1) a sound and complete deductive system to implement various types of trajectory planning, automatic generation, and validation of the CNC code; (2) a convenient design input environment and readiness for re-design and modification by adding specific design functions and using standard design procedures on a widely used CAD/CAM package; (3) helpful for designers in sheet metal layout designing, layout interference detection, process planning validation, preprocess manufacturing operation of CNC code generation, and autodefinition of storable file names; and (4) formal and simple in human–computer interaction, automatic and intelligent in process operations, and satisfactory in terms of the requirements of the flexible sheet metal machining center (BGL 130R).

We bring into attention the interplay between model theory of committed graphs (1-regular graphs) and their palindromic characteristic in the domain of formal languages. We prove some model theoretic properties of committed graphs and then give a characterization of them in the formal language domain using palindromes. We show in the first part of the paper that the theory of committed graphs and the theory of infinite committed graphs differ in terms of completeness. We give the observation that theories of finite and infinite committed graphs are both decidable. The former is finitely axiomatizable, whereas the latter is not. We note that every committed graph is isomorphic to the structure of integers. In the second part, as our main focus of the paper and using some of the results in the first section, we give a characterization of committed graphs based on the notion of finite and infinite palindrome strings.

Inspired by the efficient proof procedures discussed in {\em Computability logic} \cite{Jap03,Japic,Japfin}, we describe a heuristic proof procedure for first-order logic. This is a variant of Gentzen sequent system and has the following features: (a)~ it views sequents as games between the machine and the environment, and (b)~ it views proofs as a winning strategy of the machine. From this game-based viewpoint, a poweful heuristic can be extracted and a fair degree of determinism in proof search can be obtained. This article proposes a new deductive system LKg with respect to first-order logic and proves its soundness and completeness. We also discuss LKg', a variant of LKg with some optimizations added., Comment: 6 pages. Some optimizations are added

International audience; One of the most common scenarios of handling incomplete information occurs in relational databases. They describe in-complete knowledge with three truth values, using Kleene’s logic for propositional formulae and a rather peculiar exten-sion to predicate calculus. This design by a committee from several decades ago is now part of the standard adopted by vendors of database management systems. But is it really the right way to handle incompleteness in propositional and pred-icate logics?Our goal is to answer this question. Using an epistemic ap-proach, we first characterize possible levels of partial knowl-edge about propositions, which leads to six truth values. We impose rationality conditions on the semantics of the connec-tives of the propositional logic, and prove that Kleene’s logic is the maximal sublogic to which the standard optimization rules apply, thereby justifying this design choice. For exten-sions to predicate logic, however, we show that the additional truth values are not necessary: every many-valued extension of first-order logic over databases with incomplete informa-tion represented by null values is no more powerful than the usual two-valued logic with the standard Boolean interpreta-tion of the connectives. We use this observation to analyze the logic underlying SQL query evaluation, and conclude that the many-valued extension for handling incompleteness does not add any expressiveness to it.

International audience; BPMN is the standard for business process modeling. It includes a rich set of constructs for control-flow, inter-process communication, and time-related concerns. However, spatial concerns are left apart while being essential to several application domains. We propose a comprehensive extension of BPMN to deal with this. Our proposal includes an integrated notation, a first-order logic semantics of the extension, and tool-supported verification means through the implementation of the semantics in TLA . Our tool support and our model database are open source and freely available online.

In this paper, we compare two alternative mechanisms for deciding the validity of first-order formulas over finite domains supported by the mathematical model checker RISCAL: first, the original approach of semantic evaluation (based on an implementation of the denotational semantics of the RISCAL language) and, second, the later approach of SMT solving (based on satisfiability preserving translations of RISCAL formulas to SMT-LIB formulas as inputs for SMT solvers). After a short presentation of the two approaches and a discussion of their fundamental pros and cons, we quantitatively evaluate them, both by a set of artificial benchmarks and by a set of benchmarks taken from real-life applications of RISCAL; for this, we apply the state-of-the-art SMT solvers Boolector, CVC4, Yices, and Z3. Our benchmarks demonstrate that (while SMT solving generally vastly outperforms semantic evaluation), the various SMT solvers exhibit great performance differences. More important, we identify classes of formulas where semantic evaluation is able to compete with (or even outperform) satisfiability solving, outlining some room for improvements in the translation of RISCAL formulas to SMT-LIB formulas as well as in the current SMT technology., In Proceedings SCSS 2021, arXiv:2109.02501

Security patterns are being used in software applications to mitigate attacks occurring due to software vulnerabilities. However, developer sometimes overlooks best practices while implementing the security pattern in the software application. In this paper, authors propose a formal approach to describe various security constraints using first order predicate logic. This will facilitate the detection of security vulnerabilities at the early stages of software development life cycle. The approach has been verified using Secure Factory Pattern. The effectiveness of the approach has been further validated using Library Management System as a case study. The proposed approach will help in detection of hidden vulnerabilities in software applications.

In order to properly train a machine learning model, data must be properly collected. To guarantee a proper data collection, verifying that the collected data set holds certain properties is a possible solution. For example, guaranteeing that the data set contains samples across the whole input space, or that the data set is balanced w.r.t. different classes. We present a formal approach for verifying a set of arbitrarily stated properties over a data set. The proposed approach relies on the transformation of the data set into a first order logic formula, which can be later verified w.r.t. the different properties also stated in the same logic. A prototype tool, which uses the z3 solver, has been developed; the prototype can take as an input a set of properties stated in a formal language and formally verify a given data set w.r.t. to the given set of properties. Preliminary experimental results show the feasibility and performance of the proposed approach, and furthermore the flexibility for expressing properties of interest., Preprint submitted to IC3K 2021

Developers often rely on API documentation to learn API directives, i.e., constraints and guidelines related to API usage. Failing to follow API directives may cause defects or improper implementations. Since there are no industry-wide standards on how to document API directives, they take many forms and are often hard to understand by developers or challenging to parse with tools. In this paper, we propose a learning based approach for extracting first-order logic representations of API directives (FOL directives for short). The approach, called LEADFOL, uses a joint learning method to extract atomic formulas by identifying the predicates and arguments involved in directive sentences, and recognizes the logical relations between atomic formulas, by parsing the sentence structures. It then parses the arguments and uses a learning based method to link API references to their corresponding API elements. Finally, it groups the formulas of the same class or method together and transforms them into conjunctive normal form. Our evaluation shows that LEADFOL can accurately extract more FOL directives than a state-of-the-art approach and that the extracted FOL directives are useful in supporting code reviews.

The power communication network can be abstracted as a graph based on its topology. In this paper, we propose an approach to conduct simulations of power communication network based on its graph representation. In particular, the nodes and edges in the graph refer to the ports and channels in the grid topology. Different applications on the grid can be transformed into queries over the graph. Hence, in this paper, we build our grid simulation model based on the Neo4j graph database. We also propose a fault extension algorithm based on predicate calculus. Our experiment evaluations show that the proposed approach can effectively improve the efficiency of the power grid.

In recent years, a new approach has been developed for verifying security protocols with the aim of combining the benefits of symbolic attackers and the benefits of unconditional soundness: the technique of the computationally complete symbolic attacker of Bana and Comon (BC) [8]. In this article, we argue that the real breakthrough of this technique is the recent introduction of its version for indistinguishability [9], because, with the extensions we introduce here, for the first time, there is a computationally sound symbolic technique that is syntactically strikingly simple, to which translating standard computational security notions is a straightforward matter, and that can be effectively used for verification of not only equivalence properties but trace properties of protocols as well. We first fully develop the core elements of this newer version by introducing several new axioms. We illustrate the power and the diverse use of the introduced axioms on simple examples first. We introduce an axiom expressing the Decisional Diffie-Hellman property. We analyze the Diffie-Hellman key exchange, both in its simplest form and an authenticated version as well. We provide computationally sound verification of real-or-random secrecy of the Diffie-Hellman key exchange protocol for multiple sessions, without any restrictions on the computational implementation other than the DDH assumption. We also show authentication for a simplified version of the station-to-station protocol using UF-CMA assumption for digital signatures. Finally, we axiomatize IND-CPA, IND-CCA1, and IND-CCA2 security properties and illustrate their usage. We have formalized the axiomatic system in an interactive theorem prover, Coq, and have machine-checked the proofs of various auxiliary theorems and security properties of Diffie-Hellman and station-to-station protocol.

Team Semantics generalizes Tarski's Semantics for First Order Logic by allowing formulas to be satisfied or not satisfied by sets of assignments rather than by single assignments. Because of this, in Team Semantics it is possible to extend the language of First Order Logic via new types of atomic formulas that express dependencies between different assignments. Some of these extensions are much more expressive than First Order Logic proper; but the problem of which atoms can instead be added to First Order Logic without increasing its expressive power is still unsolved. In this work, I provide an answer to this question under the additional assumptions (true of most atoms studied so far) that the dependency atoms are relativizable and non-jumping. Furthermore, I show that the global (or Boolean) disjunction connective can be added to any strongly first order family of dependencies without increasing the expressive power, but that the same is not true in general for non strongly first order dependencies., In Proceedings GandALF 2019, arXiv:1909.05979

The expanding use of information systems in industrial and commercial settings has increased the need for interoperation between software systems. In particular, many social, industrial, and business information systems require a common basis for a seamless exchange of complex process information. This is, however, inhibited, because different systems may use distinct terminologies or assume different meanings for the same terms. A common solution to this problem is to develop logical theories that act as an intermediate language between different parties. In this article, we characterize a class of activities that can act as intermediate languages between different parties in those cases. We show that for each domain with finite number of elements there exists a class of activities, we called canonical activities, such that all possible changes within the domain can be represented as a sequence of occurrences of those activities. We use an algebraic structure for representing change and characterizing canonical activities, which enables us to abstract away domain-dependent properties of processes and activities, and demonstrate general properties of formalisms required for semantic integration of dynamic information systems.

Database-as-a-service offerings enable users to quickly create and deploy complex data processing pipelines. In practice, these pipelines often exhibit significant overlap of computation due to redundant execution of certain sub-queries. It is challenging for developers and database administrators to manually detect overlap across queries since they may be distributed across teams, organization roles, and geographic locations. Thus, we require automated cloud-scale tools for identifying equivalent queries to minimize computation overlap. State-of-the-art algebraic approaches to automated verification of query equivalence suffer from two limitations. First, they are unable to model the semantics of widely-used SQL features, such as complex query predicates and three-valued logic. Second, they have a computationally intensive verification procedure. These limitations restrict their efficacy and efficiency in cloud-scale database-as-a-service offerings. This paper makes the case for an alternate approach to determining query equivalence based on symbolic representation. The key idea is to effectively transform a wide range of SQL queries into first order logic formulae and then use satisfiability modulo theories to efficiently verify their equivalence. We have implemented this symbolic representation-based approach in EQUITAS. Our evaluation shows that EQUITAS proves the semantic equivalence of a larger set of query pairs compared to algebraic approaches and reduces the verification time by 27X. We also demonstrate that on a set of 17,461 real-world SQL queries, it automatically identifies redundant execution across 11% of the queries. Our symbolic-representation based technique is currently deployed on Alibaba's MaxCompute database-as-a-service platform.

For any query language $\mathcal {F}$ , we consider three natural families of boolean queries. Nonemptiness queries are expressed as e ≠ ∅ with e an $\mathcal {F}$ expression. Emptiness queries are expressed as e = ∅. Containment queries are expressed as e1 ⊆ e2. We refer to syntactic constructions of boolean queries as modalities. In first order logic, the emptiness, nonemptiness and containment modalities have exactly the same expressive power. For other classes of queries, e.g., expressed in weaker query languages, the modalities may differ in expressiveness. We propose a framework for studying the expressive power of boolean query modalities. Along one dimension, one may work within a fixed query language and compare the three modalities. Here, we identify crucial query features that enable us to go from one modality to another. Furthermore, we identify semantical properties that reflect the lack of these query features to establish separations. Along a second dimension, one may fix a modality and compare different query languages. This second dimension is the one that has already received quite some attention in the literature, whereas in this paper we emphasize the first dimension. Combining both dimensions, it is interesting to compare the expressive power of a weak query language using a strong modality, against that of a seemingly stronger query language but perhaps using a weaker modality. We present some initial results within this theme. The two main query languages to which we apply our framework are the algebra of binary relations, and the language of conjunctive queries.

The present article is a brief informal survey o$\textit {computability logic}$ (CoL). This relatively young and still evolving nonclassical logic can be characterized as a formal theory of computability in the same sense as classical logic is a formal theory of truth. In a broader sense, being conceived semantically rather than proof-theoretically, CoL is not just a particular theory but an ambitious and challenging long-term project for redeveloping logic. In CoL, logical operators stand for operations on computational problems, formulas represent such problems, and their "truth" is seen as algorithmic solvability. In turn, computational problems – understood in their most general, interactive sense – are defined as games played by a machine against its environment, with "algorithmic solvability" meaning existence of a machine which wins the game against any possible behavior of the environment. With this semantics, CoL provides a systematic answer to the question "What can be computed?", just like classical logic is a systematic tool for telling what is true. Furthermore, as it happens, in positive cases "What can be computed" always allows itself to be replaced by "How can be computed", which makes CoL a problem-solving tool. CoL is a conservative extension of classical first order logic but is otherwise much more expressive than the latter, opening a wide range of new application areas. It relates to intuitionistic and linear logics in a similar fashion, which allows us to say that CoL reconciles and unifies the three traditions of logical thought (and beyond) on the basis of its natural and "universal" game semantics.

In this paper we prove that $\forall \textrm{FO}$, the universal fragment of first-order logic, is superfluous in $\varSigma _2^p$ and $\varPi _2^p$. As an example, we show that this yields a syntactic proof of the $\varSigma _2^p$-completeness of value-cost satisfiability. The superfluity method is interesting since it gives a way to prove completeness of problems involving numerical data such as lengths, weights and costs and it also adds to the programme started by Immerman and Medina about the syntactic approach in the study of completeness.

In this paper we offer a formal-logical analysis of the famous reversibility objection against the Second Law of thermodynamics. We reconstruct the objection as a deductive argument leading to a contradiction, employing resources of standard quantified modal logic and thereby highlighting explicit and implicit assumptions with respect to possibility, identity, and their interaction. We then describe an alternative framework, case-intensional first order logic, that has greater expressive resources than standard quantified modal logic. We show that in that framework we can account for the role of sortals in possibility judgments. This allows us to formalize the relevant truths involved in the reversibility objection in such a way that no contradiction ensues. We claim that this analysis helps to understand in which way the Second Law is, specifically, a law of thermodynamics, but not of systems of particles in general.

Many of the existing management platforms such as pervasive computing systems implement policies that depend on dynamic operational environment changes. Existing formal approaches for automatically enforcing access control policies are primarily expressed in conventional logic programming, also known as monotonic logics, e.g., First Order Logic (FOL). The major issue with monotonic logics is that they are not devised to invalidate initial believes in the light of further observations. This limitation makes these traditional logical approaches less suitable for modeling and analyzing context-aware access control policies, where exceptional policies are introduced incrementally and adaptively during runtime. The inability to invalidate initial policies when an exception needs to be enforced might result in inconsistencies and violations that need to be resolved manually by human entities. To address the problems with conventional logical approaches and more importantly prevent such inconsistencies, this paper presents a non-monotonic logic-based reasoning scheme for modeling and analyzing adaptive access control policies. In the proposed formalism, unavailable context data and incomplete access control policies can be explicitly expressed. To do so, the paper distinguishes three kinds of policies: default, context-dependent and exception policies. The proposed formalism is based on Answer Set Programming (ASP), a non-monotonic logic programming language that allows elegant representation of unavailability of context data in adaptive systems. We devise non-monotonic policy inference rules such that, when exception policies are defined, they take precedence over default and context-dependent policies automatically. The results of two case studies are reported to demonstrate the feasibility of the proposed policy representation scheme compared to the Organizational-Based Access Control (OrBAC) model.

AGM contraction and revision assume an underlying logic that contains propositional logic. Consequently, this assumption excludes many useful logics such as the Horn fragment of propositional logic and most description logics. Our goal in this paper is to generalise AGM contraction and revision to (near-)arbitrary fragments of classical first-order logic. To this end, we first define a very general logic that captures these fragments. In so doing, we make the modest assumptions that a logic contains conjunction and that information is expressed by closed formulas or sentences. The resulting logic is called first-order conjunctive logic or FC logic for short. We then take as the point of departure the AGM approach of constructing contraction functions through epistemic entrenchment, that is the entrenchment-based contraction. We redefine entrenchment-based contraction in ways that apply to any FC logic, which we call FC contraction. We prove a representation theorem showing its compliance with all the AGM contraction postulates except for the controversial recovery postulate. We also give methods for constructing revision functions through epistemic entrenchment which we call FC revision; which also apply to any FC logic. We show that if the underlying FC logic contains tautologies then FC revision complies with all the AGM revision postulates. Finally, in the context of FC logic, we provide three methods for generating revision functions via a variant of the Levi Identity, which we call contraction, withdrawal and cut generated revision, and explore the notion of revision equivalence. We show that withdrawal and cut generated revision coincide with FC revision and so does contraction generated revision under a finiteness condition.

Inquisitive first-order logic, InqBQ, is an extension of classi- cal first-order logic with questions. From a mathematical point of view, formulas in this logic express properties of sets of relational structures. In this paper we describe an Ehrenfeucht-Fraïssé game for InqBQ and show that it characterizes the distinguishing power of the logic. We exploit this result to show a number of undefinability results: in particular, several variants of the question how many individuals have property P are not expressible in InqBQ, even in restriction to finite models.

Probabilistic databases (PDBs) are probability spaces over database instances. They provide a framework for handling uncertainty in databases, as occurs due to data integration, noisy data, data from unreliable sources or randomized processes. Most of the existing theory literature investigated finite, tuple-independent PDBs (TI-PDBs) where the occurrences of tuples are independent events. Only recently, Grohe and Lindner (PODS '19) introduced independence assumptions for PDBs beyond the finite domain assumption. In the finite, a major argument for discussing the theoretical properties of TI-PDBs is that they can be used to represent any finite PDB via views. This is no longer the case once the number of tuples is countably infinite. In this paper, we systematically study the representability of infinite PDBs in terms of TI-PDBs and the related block-independent disjoint PDBs. The central question is which infinite PDBs are representable as first-order views over tuple-independent PDBs. We give a necessary condition for the representability of PDBs and provide a sufficient criterion for representability in terms of the probability distribution of a PDB. With various examples, we explore the limits of our criteria. We show that conditioning on first order properties yields no additional power in terms of expressivity. Finally, we discuss the relation between purely logical and arithmetic reasons for (non-)representability.

Considering the fatality of phishing attacks that are emphasized by many organizations, the inductive learning approach using reported malicious URLs has been verified in the field of deep learning. However, the deep learning-based method mainly focused on the fitting of a classification task via historical URL observation shows a limitation of recall due to the characteristics of zero-day attack. In order to model the nature of a zero-day phishing attack in which URL addresses are generated and discarded immediately, an approach that utilizes the expert knowledge is promising. We introduce the integration method of deep learning and logic programmed domain knowledge to inject the real-world constraints. We design neural and logic classifiers and propose the joint learning method of each component based on the traditional neuro-symbolic integration. Extensive experiments on three real-world datasets consisting of 222,541 URLs showed the highest recall among the latest deep learning methods, despite the hostile class-imbalanced condition. We demonstrate that the optimized weighting between neural and logic component has an effect of improving the recall over 3% compared to the existing methods.

It is clear from the implementation and analysis of the performance of the game Defend and Gather and the many other examples discussed in this chapter that neural-based agents have the ability to overcome some of the shortcomings associated with implementing classical AI techniques in computer game design. Neural networks can be used in many diverse ways in computer games ranging from agent control, environmental evolution, to content generation. As outlined in Section 3 of this chapter, by following the neural network development process, adding a neural network to a computer game can be a very rewarding process. Neural networks have proven themselves viable for agent design, but there are still many unexplored avenues that could prove to benefit from neural networks in computer games. The area of content generation has only briefly been discussed in recent research. The potential is that neural networks could generate entire worlds or even entire computer games based on human players' preferences. Neural networks have great potential for designing computer games and technology that will entertain players in terms of newly generated content and increasing challenge as the players learn the game.

Traditional first-order logic has four definitions for quantifiers, which are defined by universal and existential quantifiers. In L3-valued (three-valued) first-order logic, there are eight kinds of definitions for quantifiers; and corresponding Gentzen deduction systems will be given and their soundness and completeness theorems will be proved.

Informal arguments that cryptographic protocols are secure can be made rigorous using inductive definitions. The approach is based on ordinary predicate calculus and copes with infinite-state systems. Proofs are generated using Isabelle/HOL. The human effort required to analyze a protocol can be as little as a week or two, yielding a proof script that takes a few minutes to run. Protocols are inductively defined as sets of traces. A trace is a list of communication events, perhaps comprising many interleaved protocol runs. Protocol descriptions incorporate attacks and accidental losses. The model spy knows some private keys and can forge messages using components decrypted from previous traffic. Three protocols are analyzed below: Otway-Rees (which uses shared-key encryption), Needham-Schroeder (which uses public-key encryption), and a recursive protocol by Bull and Otway (which is of variable length). One can prove that event $ev$ always precedes event $ev'$ or that property $P$ holds provided $X$ remains secret. Properties can be proved from the viewpoint of the various principals: say, if $A$ receives a final message from $B$ then the session key it conveys is good.

This paper addresses the modeling and verification analysis of the mutual relationships among plants, animals, and their environment. We start our study of mathematical ecology by considering the interaction of two species, one of which the predators eat the preys thereby affecting each other, such pairs exist throughout nature: fish and sharks, lions and gazelles, birds and insects, to mention some. Not all species form predator-prey relationships, we can also have the case of a two-species ecosystem in which both species compete for the same limited source of nutrients. If two competitors try to occupy the same realized niche, one species will try to eliminate the other. Therefore, two instances are worth to be considered. On the one hand, there is a need to cooperate sharing part of the resource so that both organisms will benefit from it. On the other hand, if one of the two species is stronger than theother, there will be no cooperation and the strongest species will imposeits conditions. In this work, the ecological interaction system between species is modeled as a formula of the first order logic. Then, using the concept of logic implication, and transforming this logical implication relation into a set of clauses, called Skolem standard form, qualitative methods for verification as well as performance issues, for some queries, are applied.

We uncover a close relationship between combinatorial and syntactic proofs for first-order logic (without equality). Whereas syntactic proofs are formalized in a deductive proof system based on inference rules, a combinatorial proof is a syntax-free presentation of a proof that is independent from any set of inference rules. We show that the two proof representations are related via a deep inference decomposition theorem that establishes a new kind of normal form for syntactic proofs. This yields (a) a simple proof of soundness and completeness for first-order combinatorial proofs, and (b) a full completeness theorem: every combinatorial proof is the image of a syntactic proof., To be published in LICS 2021. This is the author version of the paper with full proofs in the appendix