Short-term or working memory provides temporary storage of information in the brain after an experience and is associated with conscious awareness. Neurons sensitive to the multiple stimulus attributes comprising an experience are distributed within many brain regions. Such distributed cell assemblies, activated by an event, are the most plausible system to represent the WM of that event. Studies with a variety of imaging technologies have implicated widespread brain regions in the mediation of WM for different categories of information. Each kind (...) of WM may thus be expected to involve many brain regions rather than a local, uniquely dedicated set of cells. Neurons in a distributed “cell assembly” may be self-selected by their temporally coherent activations. The process by which this fragmented representation of the recent past is reassembled to accomplish essentially automatic and reliable recognition of a recurrent event constitutes an important problem. One plausible mechanism to achieve the identification of past with previous events would require that the representational system mediating WM must coexist in spatial extent and somehow overlap in temporal activation with cell ensembles registering input from subsequent events. The detection of such a postulated mechanism required an experimental approach which would focus upon spatial patterns of coherent activation while information about different events was stored in WM and retrieved, rather than focusing upon the temporal sequences of activation in localized regions of interest. For this purpose, the familiar delayed matching from sample task was modified. A series of information-free flashes, or “noncontingent probes,” was presented before an initial series of visual information items, the Priming Sample, which were to be held in WM during a Delay Period. A second series of visual information items were then presented, the Matching Sample. The task required detection of any item in the second series which had beenabsentfrom the initial series. Thirty such trials with a particular category of visual information constituted a single task. Several DMS tasks with this standardized design, but with different categories of visual information, were presented within each test session. The information categories included letters of the alphabet, single digit numbers, or faces from a school yearbook. Event-related potentials , were computed from 21 standardized electrode placements, separately for information-free probes and for information items in each interval of the trials within a task. Because each electrode is particularly sensitive to coherent activation of neurons in the immediately underlying brain regions, topographic maps were constructed and interpolated across the surface of the scalp. The momentary fluctuations of the resulting voltage “landscapes” throughout the task were then subjected to quantitative analysis. Distinctive landscapes sometimes persisted for prolonged periods, implying sustained engagement of very large populations of neurons. “Difference landscapes” were constructed by subtraction of topographic maps evoked by noncontingent probes during the Delay Period from maps of probe ERPs before the presentation of the initial information in the Priming Sample. Such probe difference landscapes displayed recurrent high similarity to momentary landscapes elicited during subsequent presentation of the information items in the Matching Sample. It seemed as if the distributed cell assembly continuously engaged by mediation of WM of the diverse attributes of the initial stimuli was being dynamically compared to the ensembles engaged by registration of the subsequent stimuli. Spatial Principal Component Analysis was applied to the sequences of momentary voltage landscapes observed throughout trials of each task. This method sought a small number of spatial patterns with which these large sets of inhomogeneous spatial distributions of voltage could be reconstructed. This is the spatial analog of the reconstruction of local ERPs by temporal principal components, as often described previously. Five Spatial Principal Components were found which accounted for about 90% of the total variance of voltage across the surface of the scalp throughout every task. Theloadings,or distinguishing topographic features, of these SPCs, were highly similar during every cognitive task for every subject. However,factor scores,or relative average contribution to the overall voltage distributions, of the different SPCs varied substantially among subjects between the tasks and momentarily within successive intervals of each task. These five SPCs may reflect coherent activation of huge distributed ensembles of neurons which comprise independent but interacting functional brain subsystems. These subsystems may correspond to basic resources available to individuals for allocation to mediate conscious evaluation of information during cognitive activity, providing a filter to bind together fractionated representations of the past to evaluate the present. (shrink)

The contents of this book, pedagogically sound and intellectually rigorous, live up to the high standards one would expect of its author. A two or three semester course based upon this book will carry the student through all of the requisite foundational material to many of the important contemporary results in recursion theory, nonstandard arithmetic, and other more esoteric areas. The book combines features of a rigorous logic text and a book on the foundations of mathematics and elementary recursion theory. (...) In the first chapter of this latter part, Kleene gives a discussion of such topics as countable sets, Cantor's diagonal method, the paradoxes, axiomatic vs. intuitive thinking in mathematics, metamathematics, formal number theory and various formal systems. The material here parallels that in Part I of the author's previous work, Introduction to Metamathematics, but is more reliant upon logic and less upon informal set theory. The chapter on recursion theory begins with the concept of the Turing machine, and then uses this to develop the incompleteness and undecidability results of Church and Gödel. Additional topics include Gödel's completeness theorem for various types of formal systems, Skolem's paradox and nonstandard arithmetic, Herbrand's theorem and Craig's interpolation theorem. Many results and theorems of the present work bear the same indexical number as the corresponding item in IM, and the book as a whole can serve as a prolegomenon to that more advanced work.—H. P. K. (shrink)

We discuss the interpolation property on some important families of non classical logics, such as intuitionistic, modal, fuzzy, and linear logics. A special paragraph is devoted to a generalization of the interpolation property, uniform interpolation.

In this article we show that bi-intuitionistic predicate logic lacks the Craig Interpolation Property. We proceed by adapting the counterexample given by Mints, Olkhovikov and Urquhart for intuitionistic predicate logic with constant domains [13]. More precisely, we show that there is a valid implication $\phi \rightarrow \psi $ with no interpolant. Importantly, this result does not contradict the unfortunately named ‘Craig interpolation’ theorem established by Rauszer in [24] since that article is about the property more correctly named ‘deductive interpolation’ (see (...) Galatos, Jipsen, Kowalski and Ono’s use of this term in [5]) for global consequence. Given that the deduction theorem fails for bi-intuitionistic logic with global consequence, the two formulations of the property are not equivalent. (shrink)

We provide a direct method for proving Craig interpolation for a range of modal and intuitionistic logics, including those containing a "converse" modality. We demonstrate this method for classical tense logic, its extensions with path axioms, and for bi-intuitionistic logic. These logics do not have straightforward formalisations in the traditional Gentzen-style sequent calculus, but have all been shown to have cut-free nested sequent calculi. The proof of the interpolation theorem uses these calculi and is purely syntactic, without resorting to embeddings, (...) semantic arguments, or interpreted connectives external to the underlying logical language. A novel feature of our proof includes an orthogonality condition for defining duality between interpolants. (shrink)

Interpolation has become one of the standard properties that logicians investigate when designing a logic. In this paper, we provide strong evidence that the presence of interpolants is not only cogent for scientific reasoning but has also important practical implications in computer science. We illustrate that interpolation in general, and uniform splitting interpolants, in particular, play an important role in applications where formality and modularity are invoked. In recognition of the fact that common logical formalisms often lack uniform interpolants, we (...) advocate the need for developing general methods to engineer a specification logic so that some critical uniform interpolants become available. (shrink)

This chapter examines global policing as it takes shape through the work of Interpol, the International Criminal Police Organization. Global policing emerges in the legal, political and technological amalgam through which transnational police cooperation is carried out, and includes the police practices inflected and made possible by this phenomenon. Interpol’s role is predominantly in the circulation of information, through which it enters into relationships and provides services that affect aspects of governance, from the local to national, regional and global. The (...) chapter describes this assemblage as a noteworthy experiment in developing what McKeon called a frame for common action. Drawing on Interpol publications, news stories, interviews with staff, and fieldwork at the General Secretariat in Lyon, France, the history, institutional structure, and daily practices are described. Three cases are analyzed, concerning Red Notices, national sovereignty, and terrorism, in order to explore some of the problems arising in Interpol’s political and technical operating arrangements. In conclusion, international and global policing are compared schematically, together with Interpol’s attempts to give institutional and procedural direction to the still-evolving form of global policing. (shrink)

A new technique is presented for proving that a consequence system enjoys Craig interpolation or Maehara interpolation based on the fact that these properties hold in another consequence system. This technique is based on the existence of a back and forth translation satisfying some properties between the consequence systems. Some examples of translations satisfying those properties are described. Namely a translation between the global/local consequence systems induced by fragments of linear logic, a Kolmogorov-Gentzen-Gödel style translation, and a new translation between (...) the global consequence systems induced by full Lambek calculus and linear logic, mixing features of a Kiriyama-Ono style translation with features of a Kolmogorov-Gentzen-Gödel style translation. These translations establish a strong relationship between the logics involved and are used to obtain new results about whether Craig interpolation and Maehara interpolation hold in that logics . (shrink)

Preservation and interpolation results are obtained for L ∞ω and sublogics $\mathscr{L} \subseteq L_{\infty\omega}$ such that equivalence in L can be characterized by suitable back-and-forth conditions on sets of partial isomorphisms.

An interpolation theorem holds for many standard modal logics, but first order $S5$ is a prominent example of a logic for which it fails. In this paper it is shown that a first order $S5$ interpolation theorem can be proved provided the logic is extended to contain propositional quantifiers. A proper statement of the result involves some subtleties, but this is the essence of it.

Continuing work initiated by Jónsson, Daigneault, Pigozzi and others; Maksimova proved that a normal modal logic (with a single unary modality) has the Craig interpolation property iff the corresponding class of algebras has the superamalgamation property (cf. [Mak 91], [Mak 79]). The aim of this paper is to extend the latter result to a large class of logics. We will prove that the characterization can be extended to all algebraizable logics containing Boolean fragment and having a certain kind of local (...) deduction property. We also extend this characterization of the interpolation property to arbitrary logics under the condition that their algebraic counterparts are discriminator varieties. We also extend Maksimova's result to normal multi-modal logics with arbitrarily many, not necessarily unary modalities, and to not necessarily normal multi-modal logics with modalities of ranks smaller than 2, too.The problem of extending the above characterization result to no n-normal non-unary modal logics remains open. (shrink)

The Interpolation Theorem, first formulated and proved by W. Craig fifty years ago for predicate logic, has been extended to many other logical frameworks and is being applied in several areas of computer science. We give a short overview, and focus on the theory of software systems and modules. An algebra of theories TA is presented, with a nonstandard interpretation of the existential quantifier . In TA, the interpolation property of the underlying logic corresponds with the quantifier combination property . (...) It is shown how the Modularization Theorem, the Factorization Lemma and the Normal Form Theorem for module expressions can be proved in TA. (shrink)

We investigate uniform interpolants in propositional modal logics from the proof-theoretical point of view. Our approach is adopted from Pitts’ proof of uniform interpolationin intuitionistic propositional logic [15]. The method is based on a simulation of certain quantifiers ranging over propositional variables and uses a terminating sequent calculus for which structural rules are admissible.

Arrow and turnstile interpolations are investigated in UCL [introduced by Sernadas et al. ], a logic that is a complete extension of classical propositional logic for reasoning about connectives that only behave as expected with a given probability. Arrow interpolation is shown to hold in general and turnstile interpolation is established under some provisos.

The Craig interpolation property is investigated for substructural logics whose algebraic semantics are varieties of semilinear pointed commutative residuated lattices. It is shown that Craig interpolation fails for certain classes of these logics with weakening if the corresponding algebras are not idempotent. A complete characterization is then given of axiomatic extensions of the “R-mingle with unit” logic that have the Craig interpolation property. This latter characterization is obtained using a model-theoretic quantifier elimination strategy to determine the varieties of Sugihara monoids (...) admitting the amalgamation property. (shrink)

We present a number of, somewhat unusual, ways of describing what Craig’s interpolation theorem achieves, and use them to identify some open problems and further directions.

In this paper we will be concerned with the interpretability logic of PA and in particular with the fact that this logic, which is denoted by ILM, does not have the interpolation property. An example for this fact seems to emerge from the fact that ILM cannot express Σ₁-ness. This suggests a way to extend the expressive power of interpretability logic, namely, by an additional operator for Σ₁-ness, which might give us a logic with the interpolation property. We will formulate (...) this extension, give an axiomatization which is modally complete and arithmetically complete (although for proofs of these theorems we refer to an earlier paper), and investigate interpolation. We show that this logic still does not have the interpolation property. (shrink)

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in restriction (...) to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

An interpolation Theorem is proved for first order logic with infinitary predicates. Our proof is algebraic via cylindric algebras.1.

We define the interpolative fusion T∪∗ of a family i∈I of first-order theories over a common reduct T∩, a notion that generalizes many examples of random or generic structures in the model-theo...

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by (...) a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]). (shrink)

We prove a generalization of Maehara’s lemma to show that the extensions of classical and intuitionistic first-order logic with a special type of geometric axioms, called singular geometric axioms, have Craig’s interpolation property. As a corollary, we obtain a direct proof of interpolation for (classical and intuitionistic) first-order logic with identity, as well as interpolation for several mathematical theories, including the theory of equivalence relations, (strict) partial and linear orders, and various intuitionistic order theories such as apartness and positive partial (...) and linear orders. (shrink)

We analyse the structure of propositional proofs in the sequent calculus focusing on the well-known procedures of Interpolation and Cut Elimination. We are motivated in part by the desire to understand why a tautology might be ‘hard to prove’. Given a proof we associate to it a logical graph tracing the flow of formulas in it . We show some general facts about logical graphs such as acyclicity of cut-free proofs and acyclicity of contraction-free proofs , and we give a (...) proof of a strengthened version of the Craig Interpolation Theorem based on flows of formulas. We show that tautologies having minimal interpolants of non-linear size must have proofs with certain precise structural properties. We then show that given a proof Π and a cut-free form Π′ associated to it , certain subgraphs of Π′ which are logical graphs correspond to subgraphs of Π which are logical graphs for the same sequent. This locality property of cut elimination leads to new results on the complexity of interpolants, which cannot follow from the known constructions proving the Craig Interpolation Theorem. (shrink)

Decision theory requires agents to assign probabilities to states of the world and utilities to the possible outcomes of different actions. When agents commit to having the probabilities and/or utilities in a decision problem defined by objective features of the world, they may find themselves unable to decide which actions maximize expected utility. Decision theory has long recognized that work-around strategies are available in special cases; this is where dominance reasoning, minimax, and maximin play a role. Here we describe a (...) different work around, wherein a rational decision about one decision problem can be reached by ‘interpolating’ information from another problem that the agent believes has already been rationally solved. (shrink)

In a previous paper [ 21 ] all extensions of Johansson’s minimal logic J with the weak interpolation property WIP were described. It was proved that WIP is decidable over J. It turned out that the weak interpolation problem in extensions of J is reducible to the same problem over a logic Gl, which arises from J by adding tertium non datur. In this paper we consider extensions of the logic Gl. We prove that only finitely many logics over Gl (...) have the Craig interpolation property CIP, the restricted interpolation property IPR or the projective Beth property PBP. The full list of Gl-logics with the mentioned properties is found, and their description is given. We note that IPR and PBP are equivalent over Gl. It is proved that CIP, IPR and PBP are decidable over the logic Gl. (shrink)

The provability logic GL was in the field of interest of A.V. Kuznetsov, who had also formulated its intuitionistic analog—the intuitionisticprovability logic—and investigated these two logics and their extensions.In the present paper, different versions of interpolation and of the Bethproperty in normal extensions of the provability logic GL are considered. Itis proved that in a large class of extensions of GL almost all versions of interpolation and of the Beth propertyare equivalent. It follows that in finite slice logics over GL (...) the three versionsCIP, IPD and IPR of the interpolation property are equivalent. Also theyare equivalent to the Beth properties B1, PB1 and PB2. (shrink)

In a recent paper we have defined an analytic tableau calculus PL_16 for a functionally complete extension of Shramko and Wansing's logic based on the trilattice SIXTEEN_3. This calculus makes it possible to define syntactic entailment relations that capture central semantic relations of the logic---such as the relations |=_t, |=_f, and |=_i that each correspond to a lattice order in SIXTEEN_3; and |=, the intersection of |=_t and |=_f,. -/- It turns out that our method of characterising these semantic relations---as (...) intersections of auxiliary relations that can be captured with the help of a single calculus---lends itself well to proving interpolation. All entailment relations just mentioned have the interpolation property, not only when they are defined with respect to a functionally complete language, but also in a range of cases where less expressive languages are considered. For example, we will show that |=, when restricted to L_{tf}, the language originally considered by Shramko and Wansing, enjoys interpolation. This answers a question that was recently posed by M. Takano. (shrink)

Craig's interpolation lemma (if φ → ψ is valid, then φ → θ and θ → ψ are valid, for θ a formula constructed using only primitive symbols which occur both in φ and ψ) fails for many propositional and first order modal logics. The interpolation property is often regarded as a sign of well-matched syntax and semantics. Hybrid logicians claim that modal logic is missing important syntactic machinery, namely tools for referring to worlds, and that adding such machinery solves (...) many technical problems. The paper presents strong evidence for this claim by defining interpolation algorithms for both propositional and first order hybrid logic. These algorithms produce interpolants for the hybrid logic of every elementary class of frames satisfying the property that a frame is in the class if and only if all its point-generated subframes are in the class. In addition, on the class of all frames, the basic algorithm is conservative: on purely modal input it computes interpolants in which the hybrid syntactic machinery does not occur. (shrink)

We investigate interpolation properties of many-valued propositional logics related to continuous t-norms. In case of failure of interpolation, we characterize the minimal interpolating extensions of the languages. For finite-valued logics, we count the number of interpolating extensions by Fibonacci sequences.

Craig interpolation theorem implies that the derivability of X,X′ Y′ implies existence of an interpolant I in the common language of X and X′ Y′ such that both X I and I,X′ Y′ are derivable. For classical logic this extends to X,X′ Y,Y′, but for intuitionistic logic there are counterexamples. We present a version true for intuitionistic propositional logic, and more complicated version for the predicate case.

We show that the feasible interpolation property is robust for some proof systems but not for others.

A (normalized) interpolant I in Craig's theorem is a kind of explanation why the consequence relation (from F to G) holds. This is because I is a summary of the interaction of the configurations specified by F and G, respectively, that shows how G follows from F. If explaining E means deriving it from a background theory T plus situational information A and if among the concepts of E we can separate those occurring only in T or only in A, (...) then the interpolation theorem applies in two different ways yielding two different explanations and two different covering laws. (shrink)

In this paper by using a model-theoretic approach, we prove Craig interpolation property for Formal Propositional Logic, FPL, Basic propositional logic, BPL and the uniform left-interpolation property for FPL. We also show that there are countably infinite extensions of FPL with the uniform interpolation property.

A method is presented that connects the existence of uniform interpolants to the existence of certain sequent calculi. This method is applied to several modal logics and is shown to cover known results from the literature, such as the existence of uniform interpolants for the modal logic \. New is the result that \ has uniform interpolation. The results imply that for modal logics \ and \, which are known not to have uniform interpolation, certain sequent calculi cannot exist.

We prove that certain natural sequent systems for bi-intuitionistic logic have the analytic cut property. In the process we show that the (global) subformula property implies the (local) analytic cut property, thereby demonstrating their equivalence. Applying a version of Maehara technique modified in several ways, we prove that bi-intuitionistic logic enjoys the classical Craig interpolation property and Maximova variable separation property; its Halldén completeness follows.

The splitting theorem says that any set of formulae has a finest representation as a family of letter-disjoint sets. Parikh formulated this for classical propositional logic, proved it in the finite case, used it to formulate a criterion for relevance in belief change, and showed that AGMpartial meet revision can fail the criterion. In this paper we make three further contributions. We begin by establishing a new version of the well-known interpolation theorem, which we call parallel interpolation, use it to (...) prove the splitting theorem in the infinite case, and show how AGM belief change operations may be modified, if desired, so as to ensure satisfaction of Parikh’s relevance criterion. (shrink)

Several extensions of the basic modal language are characterized in terms of interpolation. Our main results are of the following form: Language ℒ' is the least expressive extension of ℒ with interpolation. For instance, let ℳ be the extension of the basic modal language with a difference operator [7]. First-order logic is the least expressive extension of ℳ with interpolation. These characterizations are subsequently used to derive new results about hybrid logic, relation algebra and the guarded fragment.

We show in this paper that all fragments of intuitionistic propostional logic based on a subset of the connectives $\wedge, \vee, \rightarrow, \neg$ satisfy interpolation. Fragments containing $\leftrightarrow$ or $\neg\neg$ are briefly considered.

The Craig interpolation property and interpolation property for deducibility are considered for special kind of normal extensions of the Brouwer logic.

We provide three new results about interpolating 2-r.e. or 2-REA degrees between given r.e. degrees: Proposition 1.13. If c h are r.e. , c is low and h is high, then there is an a h which is REA in c but not r.e. Theorem 2.1. For all high r.e. degrees h g there is a properly d-r.e. degree a such that h a g and a is r.e. in h . Theorem 3.1. There is an incomplete nonrecursive r.e. A (...) such that every set REA in A and recursive in 0′ is of r. e. degree. The first proof is a variation on the construction of Soare and Stob . The second combines highness with a modified version of the proof strategy of Cooper et al. . The third theorem is a rather surprising result with a somewhat unusual proof strategy. Its proof is a 0‴ argument that at times moves left in the tree so that the accessible nodes are not linearly ordered at each stage. Thus the construction lacks a true path in the usual sense. Two substitute notions fill this role: The true nodes are the leftmost ones accessible infinitely often; the semitrue nodes are the leftmost ones such that there are infinitely many stages at which some extension is accessible. Another unusual feature of the construction is that it involves using distinct priority orderings to control the interactions of different parts of the construction. (shrink)