We give a sound and complete axiomatization for the full computation tree logic, CTL*, of R-generable models. This solves a long standing open problem in branching time temporal logic.

It is known that the full computation-tree logic CTL * is an important base logic for model checking. The bisimulation theorem for CTL* is known to be useful for abstraction in model checking. In this paper, the bisimulation theorems for two paraconsistent four-valued extensions 4CTL* and 4LCTL* of CTL* are shown, and a translation from 4CTL* into CTL* is presented. By using 4CTL* and 4LCTL*, inconsistency-tolerant and spatiotemporal reasoning can be expressed as a model checking framework.

It is known that the full computation-tree logic CTL∗is an important base logic for model checking. The bisimulation theorem for CTL∗is known to be useful for abstraction in model checking. In this paper, thebisimulation theorems for two paraconsistent four-valued extensions 4CTL∗and 4LCTL∗of CTL∗are shown, and a translation from 4CTL∗into CTL∗ispresented. By using 4CTL∗and 4LCTL∗, inconsistency-tolerant and spatiotemporal reasoning can be expressed as a model checking framework.

ABSTRACT A complete axiomatic system CTLrp is introduced for a temporal logic for finitely branching ω+ -trees in a language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL* into CTLrp. In particular, that yields a complete axiomatization for the translations of all valid CTL*-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a (...) way more expressive medium for reasoning about branching time. (shrink)

A complete axiomatic system CTL$_{rp}$ is introduced for a temporal logic for finitely branching $\omega^+$-trees in a temporal language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL$^{*}$ into CTL$_{rp}$. In particular, that yields a complete axiomatization for the translations of all valid CTL$^{*}$-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a way (...) more expressive medium for reasoning about branching time. (shrink)

Makkai [10] produced an arithmetical structure of Scott rank $\omega _{1}^{\mathit{CK}}$. In [9]. Makkai's example is made computable. Here we show that there are computable trees of Scott rank $\omega _{1}^{\mathit{CK}}$. We introduce a notion of "rank homogeneity". In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated "group trees" of [10] and [9]. Using the same kind of trees, we obtain one of rank (...) $\omega _{1}^{\mathit{CK}}$ that is "strongly computably approximable". We also develop some technology that may yield further results of this kind. (shrink)

We divide the class of infinite computable trees into three types. For the first and second types, 0' computes a nontrivial self-embedding while for the third type 0'' computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite Π01 antichain. This result is optimal and has (...) connections to the program of reverse mathematics. (shrink)

Query processing in ground definite deductive is known to correspond precisely to a linear programming problem. However, the “groundedness” requirement is a huge drawback to using linear programming techniques for logic program computations because the ground version of a logic program can be very large when compared to the original program. Furthermore, when we move from propositional logic programs to first-order logic programs, this effectively means that functions symbols may not occur in clauses. In this paper, (...) we develop a theory of “instantiate- by-need” that performs instantiations only when needed. We prove that this method is sound and complete when computing answer substitutions for non-ground logic programs including those containing function symbols. More importantly, when taken in conjunction with Colmerauer's result that unification can be viewed as linear programming, this means that resolution with unification can be completely replaced by linear programming as an operational paradigm. Additionally, our tree construction method is not rigidly tied to the linear programming paradigm-we will show that given any method M that can compute the set of atomic logical consequences of a propositional logic program, our method can use M to compute , the set of all atoms that are consequences of a first-order logic program. (shrink)

This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its applications and thus presents (...) the state of the art in the area. (shrink)

We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.

We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n≥ 1 in ω, there exists a computable tree of finite height which is δ0n+1-categorical (...) but not δ0n-categorical. (shrink)

Computability, while usually performed within the context of ω, may be extended to larger ordinals by means of α-recursion. In this article, we concentrate on the particular case of ω1-recursion, and study the differences in the behavior of ${\rm{\Pi }}_1^0$-classes between this case and the standard one.Of particular interest are the ${\rm{\Pi }}_1^0$-classes corresponding to computable trees of countable width. Classically, it is well-known that the analog to König’s Lemma—“every tree of countable width and uncountable height has an uncountable (...) branch”—fails; we demonstrate that not only does it fail effectively, but also that the failure is as drastic as possible. This is proven by showing that the ω1-Turing degrees of even isolated paths in computable trees of countable width are cofinal in the ${\rm{\Delta }}_1^1\,{\omega _1}$-Turing degrees.Finally, we consider questions of nonisolated paths, and demonstrate that the degrees realizable as isolated paths and the degrees realizable as nonisolated ones are very distinct; in particular, we show that there exists a computable tree of countable width so that every branch can only be ω1-Turing equivalent to branches of trees with ${\aleph _2}$-many branches. (shrink)

The tense tree method extends Jeffrey’s well-known formulation of classical propositional logic to tense logic (Jeffrey 1991).1 Tense trees combine pure tense logic with features of Prior’s U-calculi (where ‘U’ is the earlier-than relation; see Prior 1967 and the Introduction to this volume). The tree method has a number of virtues: trees are well suited to computational applications; semantically, the tree systems presented here are no less illuminating than model theory; the metatheory associated with (...) tree formulations is often more tractable than that required in a model-theoretic setting; and last but not least the tree method is ideal for pedagogical purposes. (shrink)

For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes (...) under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. (shrink)

We study the position of the computable setting in the “common theory of locality” developed in [4, 5] for local problems on $\Delta $ -regular trees, $\Delta \in \omega $. We show that such a problem admits a computable solution on every highly computable $\Delta $ -regular forest if and only if it admits a Baire measurable solution on every Borel $\Delta $ -regular forest. We also show that if such a problem admits a computable solution on every computable maximum (...) degree $\Delta $ forest then it admits a continuous solution on every maximum degree $\Delta $ Borel graph with appropriate topological hypotheses, though the converse does not hold. (shrink)

A sufficient condition for an extension of positive logic with strong negation to be characterized by a class of finite trees is given.

This paper presents a method to compute a posteriori probability intervals when the initial conditional information is also given with probability intervals. The right way to make an exact computation is with the associated convex set of probabilities. Probability trees are used to represent these initial conditional convex sets because they greatly save the space required. This paper proposes a simulated annealing algorithm, which uses probability trees to represent the convex sets in order to compute the a posteriori intervals.

We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.

In this paper we show the adequacy of tense logic with unary operators for dealing with finite trees. We prove that models on finite trees can be characterized by tense formulas, and describe an effective method to find an axiomatization of the theory of a given finite tree in tense logic. The strength of the characterization is shown by proving that adding the binary operators "Until" and "Since" to the language does not result in a better description (...) than that given by unary tense logic; although the greater expressive power of "Until" and "Since" can be exploited by using the semantics of e-frames instead of traditional Kripke semantics. (shrink)

In their simplest form, hybrid languages are propositional modal languages which can refer to states. They were introduced by Arthur Prior, the inventor of tense logic, and played an important role in his work: because they make reference to specific times possible, they remove the most serious obstacle to developing modal approaches to temporal representation and reasoning. However very little is known about the computational complexity of hybrid temporal logics.In this paper we analyze the complexity of the satisfiability problem (...) of a number of hybrid temporal logics: the basic hybrid language over transitive trees; nominal Until logic; and referential interval logic. We discuss the effects of including nominals, the @ operator, the somewhere modality E, and the difference operator D. Adding nominals to tense logic leads for several frame-classes to an increase in complexity of the satisfiability problem from PSPACE to EXPTIME. On transitive trees, however, the satisfiability problem for this language can be decided in PSPACE. Along the way we make a detour through hybrid propositional dynamic logic: we establish upper bounds for a number of temporal logics by generalizing results due to Passy and Tinchev [29] and De Giacomo [16]. We conclude with some remarks on the relevance of our results to description logic, and draw attention to the utility of the spypoint technique for proving upper and lower bounds. (shrink)

An intermediate predicate logic L is called finite iff it is characterized by a finite partially ordered set M, i.e., iff L is the logic of the class of all predicate Kripke frames based on M. In this paper we study axiomatizability of logics of this kind. Namely, we consider logics characterized by finite trees M of a certain type (levelwise uniform trees) and establish the finite axiomatizability criterion for this case.

Tylman has recently pointed out some striking conceptual and methodological analogies between philosophy and computer science. In this paper, I focus on one of Tylman’s most convincing cases, viz. the similarity between Plato’s theory of Ideas and the object-oriented programming paradigm, and analyze it in some more detail. In particular, I argue that the platonic doctrine of the Porphyrian tree corresponds to the fact that most object-oriented programming languages do not support multiple inheritance. This analysis further reinforces Tylman’s point (...) regarding the conceptual continuity between classical metaphysical theorizing and contemporary computer science. (shrink)

An important link between model theory and proof theory is to construe a deductive disproof of S as an attempted construction of a countermodel to it. In the function logic outlined here, this idea is implemented in such a way that different kinds of individuals can be introduced into the countermodel in any order whatsoever. This imposes connections between the length of the branches of the tree that a disproof is and their number. If there are already n (...) individuals in the countermodel that is being constructed, the next individual has to be considered in its relations to each of the n old ones, creating 2^n different cases and accordingly at least 2^n different branches. Hence a disproof procedure of a polynomial length is normally not equivalent with an exponential one. Because every computation can be represented as a deduction with the same number of constant terms, the same holds for nondeterministic computations. Apparent exceptions seem to come about if a branch created by a new individual i is redundant. But when the disproof is a shortest one (contains the minimum number of different constant terms) then not introducing that idle term at all would result in an even shorter disproof, violating the shortness assumption. (shrink)

This article discusses ways to operationalise the concept of culturally appropriate computer-mediated communication, utilising information systems (IS) development methodologies and adopting a postmodern and postcolonial perspective. By way of illustration, it describes progress on the participative development of the Ieramugadu Cultural Information System. This project is designed to develop and evaluate innovative procedures for elicitation, analysis, storage and communication of indigenous cultural heritage information. It is investigating culturally appropriate IS design techniques, multimedia approaches and ways to ensure protection of secret/sacred (...) information. Ethical issues are foregrounded. (shrink)

There is an exponential speed-up in the number of lines of the quantified propositional sequent calculus over Substitution Frege Systems, if one considers proofs as trees. Whether this is true also for the number of symbols, is still an open problem.

Evolutionary and organismal biology have become inundated with data. At the same rate, we are experiencing a surge in broader evolutionary and ecological syntheses for which tree-thinking is the staple for a variety of post-tree analyses. To fully take advantage of this wealth of data to discover and understand large-scale evolutionary and ecological patterns, computational data integration, i.e., the use of machines to link data at large scale, is crucial. The most common shared entity by which evolutionary and (...) ecological data need to be linked is the taxon to which they belong. We propose a set of requirements that a system for defining such taxa should meet for computational data science: taxon definitions should maintain conceptual consistency, be reproducible via a known algorithm, be computationally automatable, and be applicable across the Tree of Life. We argue that Linnaean names, the most prevalent means of linking data to taxa, fail to meet these requirements due to fundamental theoretical and practical shortfalls. We argue that for the purposes of data-integration we should instead use phylogenetic definitions transformed into formal logic expressions. We call such expressions “phyloreferences”, and argue that, unlike Linnaean names, they meet all requirements for effective data-integration. (shrink)

In this paper we first give a variant of a theorem of Jockusch–Lewis– Remmel on existence of a computable, degree-preserving homeomorphism between a bounded strong ${\Pi^0_2}$ class and a bounded ${\Pi^0_1}$ class in 2 ω . Namely, we show that for mathematically common and interesting topological spaces, such as computably presented ${\mathbb{R}^n}$ , we can obtain a similar result where the homeomorphism is in fact the identity mapping. Second, we apply this finding to give a new, priority-free proof of existence (...) of a tree of shadow points computable in 0′. (shrink)

Since its conception nearly 20 years ago, Logic Programming - the idea of using logic as a programming language - has been developed to the point where it now plays an important role in areas such as database theory, artificial intelligence and software engineering. However, there are still many challenging research issues to be addressed and the UK branch of the Association for Logic Programming was set up to provide a forum where the flourishing research community could (...) discuss important issues of Logic Programming which were often by-passed at the large international conferences. This volume contains the twelve papers which were presented at the ALPUK's 3rd conference which was held in Edinburgh, 10-12 April 1991. The aim of the conference was to give a broad but detailed technical insight into the work currently being done in this field, both in the UK and by researchers as far afield as Canada and Bulgaria. The breadth of interest in this area of Computer Science is reflected in the range of the papers which cover - amongst other areas - massively parallel implementation, constraint logic programming, circuit modelling, algebraic proof of program properties, deductive databases, specialised editors and standardisation. The resulting volume gives a good overview of the current progress being made in the field and will be of interest to researchers and students of any aspects of logic programming, parallel computing or database techniques and management. (shrink)

Numbers. Natural numbers -- Integers -- Real numbers -- Irrational and transcendental numbers -- Funny numbers. Zero -- e : the unnatural natural number -- [Phi] : the golden ratio -- i : the imaginary number -- Writing numbers. Roman numerals -- Egyptian fractions -- Continued fractions -- Logic. Mr. Spock is not logical -- Proofs, truth, and trees : oh my! -- Programming with logic -- Temporal reasoning -- Sets. Cantor's diagonalization : infinity isn't just infinity -- (...) Axiomatic set theory : keep the good, dump the bad -- Models : using sets as the LEGOs of the math world -- Transfinite numbers : counting and ordering infinite sets -- Group theory : finding symmetries with sets -- Mechanical math. Finite state machines : simplicity goes far -- The turing machine -- Pathology and the heart of computing -- Calculus : no, not that calculus- [lambda] calculus -- Numbers, booleans, and recursion -- Types, types, types : modeling [lambda] calculus -- The halting problem. (shrink)

We draw parallels between several closely related logics that combine — in different proportions — elements of game theory, computation tree logics, and epistemic logics to reason about agents and their abilities. These are: the coalition game logics CL and ECL introduced by Pauly 2000, the alternating-time temporal logic ATL developed by Alur, Henzinger and Kupferman between 1997 and 2002, and the alternating-time temporal epistemic logic ATEL by van der Hoek and Wooldridge (2002). In particular, we (...) establish some subsumption and equivalence results for their semantics, as well as interpretation of the alternating-time temporal epistemic logic into ATL. The focus in this paper is on models: alternating transition systems, multi-player game models (alias concurrent game structures) and coalition effectivity models turn out to be intimately related, while alternating epistemic transition systems share much of their philosophical and formal apparatus. Our approach is constructive: we present ways to transform between different types of models and languages. (shrink)

A new method for obtaining lower bounds on the computational complexity of logical theories is presented. It extends widely used techniques for proving the undecidability of theories by interpreting models of a theory already known to be undecidable. New inseparability results related to the well known inseparability result of Trakhtenbrot and Vaught are the foundation of the method. Their use yields hereditary lower bounds . By means of interpretations lower bounds can be transferred from one theory to another. Complicated machine (...) codings are replaced by much simpler definability considerations, viz., the kinds of binary relations definable with short formulas on large finite sets. Numerous examples are given, including new proofs of essentially all previously known lower bounds for theories, and lower bounds for various theories of finite trees, which turn out to be particularly useful. (shrink)

Each of our theories of mental representation provides some insight into how the mind works. However, these insights often seem incompatible, as the debates between symbolic, dynamical, emergentist, sub-symbolic, and grounded approaches to cognition attest. Mental representations—whatever they are—must share many features with each of our theories of representation, and yet there are few hypotheses about how a synthesis could be possible. Here, I develop a theory of the underpinnings of symbolic cognition that shows how sub-symbolic dynamics may give rise (...) to higher-level cognitive representations of structures, systems of knowledge, and algorithmic processes. This theory implements a version of conceptual role semantics by positing an internal universal representation language in which learners may create mental models to capture dynamics they observe in the world. The theory formalizes one account of how truly novel conceptual content may arise, allowing us to explain how even elementary logical and computational operations may be learned from a more primitive basis. I provide an implementation that learns to represent a variety of structures, including logic, number, kinship trees, regular languages, context-free languages, domains of theories like magnetism, dominance hierarchies, list structures, quantification, and computational primitives like repetition, reversal, and recursion. This account is based on simple discrete dynamical processes that could be implemented in a variety of different physical or biological systems. In particular, I describe how the required dynamics can be directly implemented in a connectionist framework. The resulting theory provides an “assembly language” for cognition, where high-level theories of symbolic computation can be implemented in simple dynamics that themselves could be encoded in biologically plausible systems. (shrink)

Our main result is that there exist structures which cannot be computably recovered from their tree of tuples. This implies that there are structures with no computable copies which nevertheless cannot code any information in a natural/functorial way.

The Joint International Conference on Logic Programming, sponsored by the Association for Logic Programming, is a major forum for presentations of research, applications, and implementations in this important area of computer science. Logic programming is one of the most promising steps toward declarative programming and forms the theoretical basis of the programming language Prolog and its various extensions. Logic programming is also fundamental to work in artificial intelligence, where it has been used for nonmonotonic and commonsense (...) reasoning, expert systems implementation, deductive databases, and applications such as computer-aided manufacturing. Krzysztof R. Apt is project leader at the Centre for Mathematics and Computer Science in Amsterdam and part-time Professor in Computer Science at the University of Amsterdam. Topics covered: Theory Foundations. Programming Languages. Implementation. Programming Methodologies and Tools. Applications. Deductive Databases. Artificial Intelligence. Parallelism. (shrink)

Logic is essential to correct reasoning and also has important theoretical applications in philosophy, computer science, linguistics, and mathematics. This book provides an exceptionally clear introduction to classical logic, with a unique approach that emphasizes both the hows and whys of logic. Here Nicholas Smith thoroughly covers the formal tools and techniques of logic while also imparting a deeper understanding of their underlying rationales and broader philosophical significance. In addition, this is the only introduction to (...) class='Hi'>logic available today that presents all the major forms of proof--trees, natural deduction in all its major variants, axiomatic proofs, and sequent calculus. The book also features numerous exercises, with solutions available on an accompanying website. -/- Logic is the ideal textbook for undergraduates and graduate students seeking a comprehensive and accessible introduction to the subject. -/- Provides an essential introduction to classical logic Emphasizes the how and why of logic Covers both formal and philosophical issues Presents all the major forms of proof--from trees to sequent calculus Features numerous exercises, with solutions available online The ideal textbook for undergraduates and graduate students . (shrink)

The satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations. It is shown that FO 2 over ordered, respectively wellordered, domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems is (...) essentially the same as for plain unconstrained FO 2 , namely non-deterministic exponential time. In contrast FO 2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings, wellorderings, or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO 2 and computation tree logic CTL. (shrink)

The First International Workshop brings together researchers from the theoretical ends of the logic programming and artificial intelligence communities to discuss their mutual interests. Logic programming deals with the use of models of mathematical logic as a way of programming computers, where theoretical AI deals with abstract issues in modeling and representing human knowledge and beliefs. One common ground is nonmonotonic reasoning, a family of logics that includes room for the kinds of variations that can be found (...) in human reasoning. Topics covered: Stable Semantics. Default Logic. AutoEpistemic Logic. Truth Maintenance Systems. Implementation Issues. Diagnosis. Applications. Inheritance Reasoning. Logics of Belief. Inconsistency and Non-Monotonicity. (shrink)

The electric activities of cortical pyramidal neurons are supported by structurally stable, morphologically complex axo-dendritic trees. Anatomical differences between axons and dendrites in regard to their length or caliber reflect the underlying functional specializations, for input or output of neural information, respectively. For a proper assessment of the computational capacity of pyramidal neurons, we have analyzed an extensive dataset of three-dimensional digital reconstructions from the NeuroMorphoOrg database, and quantified basic dendritic or axonal morphometric measures in different regions and layers of (...) the mouse, rat or human cerebral cortex. Physical estimates of the total number and type of ions involved in neuronal electric spiking based on the obtained morphometric data, combined with energetics of neurotransmitter release and signaling fueled by glucose consumed by the active brain, support highly efficient cerebral computation performed at the thermodynamically allowed Landauer limit for implementation of irreversible logical operations. Individual proton tunneling events in voltage-sensing S4 protein alpha-helices of Na+, K+ or Ca2+ ion channels are ideally suited to serve as single Landauer elementary logical operations that are then amplified by selective ionic currents traversing the open channel pores. This miniaturization of computational gating allows the execution of over 1.2 zetta logical operations per second in the human cerebral cortex without combusting the brain by the released heat. (shrink)

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

Non-well-founded trees are used in mathematics and computer science, for modelling non-well-founded sets, as well as non-terminating processes or infinite data structures. Categorically, they arise as final coalgebras for polynomial endofunctors, which we call M-types. We derive existence results for M-types in locally cartesian closed pretoposes with a natural numbers object, using their internal logic. These are then used to prove stability of such categories with M-types under various topos-theoretic constructions; namely, slicing, formation of coalgebras , and sheaves for (...) an internal site. (shrink)