Search

This is a survey on fixed points of endofunctors, including initial algebras and terminal coalgebras. We also consider the rational fixed point, a canonical domain of behavior for finitely presentable systems. In addition to the basic existence theorems for fixed points, several new results are presented. For example, the Smyth–Plotkin theorem that locally continuous endofunctors of DCPO have terminal coalgebras is derived from a new result stating that every locally monotone endofunctor with a fixed point has a terminal coalgebra. We introduce bounded endofunctors on abstract categories and prove that they have terminal coalgebras. We study well-founded coalgebras and prove that for set functors, the largest well-founded coalgebra of every fixed point is the initial algebra. Another new result concerns mixed fixed points: initial algebras and terminal coalgebras of a parametrized accessible functor always form accessible functors.

§1. Introduction. Our understanding of Nature comes in layers, so should the development of logic. Classic logic is an indispensable part of our knowledge, and its interactions with computer science have recently dramatically changed our life. A new layer of logic has been developing ever since the discovery of quantum mechanics. G. D. Birkhoff and von Neumann introduced quantum logic in a seminal paper in 1936 [1]. But the definition of quantum logic varies among authors (see [2]). How to capture the logic structure inherent in quantum mechanics is very interesting and challenging. Given the close connection between classical logic and theoretical computer science as exemplified by the coincidence of computable functions through Turing machines, recursive function theory, and ?-calculus, we are interested in how to gain some insights about quantum logic from quantum computing. In this note we make some observations about quantum logic as motivated by quantum computing (see [5]) and hope more people will explore this connection.The quantum logic as envisioned by Birkhoff and von Neumann is based on the lattice of closed subspaces of a Hilbert space, usually an infinite dimensional one. The quantum logic of a fixed Hilbert space H in this note is the variety of all the true equations with finitely many variables using the connectives meet, join and negation. Quantum computing is theoretically based on quantum systems with finite dimensional Hilbert spaces, especially the states space of a qubit C2. (Actually the qubit is merely a convenience.

Abstract In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 S11–complete. Two of these fragments do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 S01–complete. These results go via reduction to problems concerning domino systems.

One of the interesting trends in theoretical computer science in recent years is the turn towards new application areas. It is not strange to see career shifts from complexity theory to cryptography, from type theory to security, from formal language theory to computational biology. The trend is reflected in journals as well. For example, the newly-open-for-business electronic journal Logical Methods in Computer Science has editors in the "emerging topics" of quantum computation and logic, and in computational systems in biology. Theoretical Computer Science recently added to its two sections (algorithms, automata, complexity and games; and logic, semantics and theory of programming) a third section entitled "Natural Computing". This "is devoted to the study of computing occurring in nature and computing inspired by nature. ... it will contain papers dealing with the theoretical issues in evolutionary computing, neural networks, molecular computing, and quantum computing." (Interstingly, SIGACT News seems to be immune from this trend, at least so far.) Finally, we turn from official journals to decidedly unofficial sources: weblogs summaries of panel discussions at conferences. On May 14, 2004, the Columbia/IBM Research/NYU Theory Day held a panel on "The Future of CS Theory." As reported in Lance Fornow's Computational Complexity Web Log, Richard Karp "highlighted three areas of interest for the future: (1) the study of large scale distributed systems such as the Web, incorporating ideas from economics and game theory; (2) connections with areas of natural science, ranging from statistical physics to quantum mechanics to biology; and (3) the 'new face' of AI in which stochastic and graphical models and statistical inference are playing a big role."

G: has property if whenever F and H are connected graphs with and |H|=|F|+1, and and are isometric embeddings, then there is an isometric embedding such that . It is easy to construct an infinite graph with for all k, and holds in almost all finite graphs. Prior to this work, it was not known whether there exist any finite graphs with . We show that the Johnson graphs J(n,3) satisfy whenever , and that J(6,3) is the smallest graph satisfying . We also construct finite graphs satisfying and local versions of the extension axioms studied in connection with the Rado universal graph.

This paper studies model theoretic conditions that arise in the study of distanced graphs. These are graphs with additional relation symbols for finite distances. Every embedding of distanced graphs is an isometric embedding. The conditions we study are the version of homogeneity, injectivity and universality for distanced graphs. There is a countable graph which isometrically embeds every countable graph. There is a unique countable distace homogeneous graph with this universal property. Its first-order theory is the model completion of the theory of distanced graphs. It has a unique countable connected model, but it has more than one connected model of each uncountable cardinality.

AbstractWe study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in “propositional” fragments of the functional language of recursionFLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The “pure,” propositional fragment FLR0turns out to coincide with the iteration theoriesof [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.

We present a rendering of some common grammatical formalisms in terms of evolving algebras. Though our main concern in this paper is on constraint-based formalisms, we also discuss the more basic case of context-free grammars. Our aim throughout is to highlight the use of evolving algebras as a specification tool to obtain grammar formalisms.

We consider the use ofevolving algebra methods of specifying grammars for natural languages. We are especially interested in distributed evolving algebras. We provide the motivation for doing this, and we give a reconstruction of some classic grammar formalisms in directly dynamic terms. Finally, we consider some technical questions arising from the use of direct dynamism in grammar formalisms.

The articles in this part of this issue of the journal are a selection of the papers originally presented to the Fifth Workshop on Coalgebraic Methods in Computer Science. CMCS was held in April 2002, in Grenoble, France as a satellite conference of ETAPS. The conference proceedings were published in Electronic Notes in Theoretical Computer Science65 (1). There were fifteen contributed papers and two invited talks. Six papers were selected by the Program Committee after a meeting for consideration of this issue, and revised versions were then sent to referees. In consultation with them, I selected the four published here. Most of them were later revised, so, in general, the papers appearing here are improved versions of the conference versions.