16th International Symposium on Fundamentals of
Computation Theory
August 27-30, 2007, Budapest, Hungary

Invited Speakers

    Ahmed Bouajjani (Paris, France)
    Rewriting Systems with Data: A Framework for Reasoning about Systems with Unbounded Structures over Infinite Data Domains (with P. Habermehl, Y. Jurski, and M. Sighireanu)

      We introduce a uniform framework for reasoning about infinite-state systems with unbounded control structures and unbounded data domains. Our framework is based on constrained rewriting systems on words over an infinite alphabet. We consider several rewriting semantics: factor, prefix, and multiset rewriting. Constraints are expressed in a logic on such words which is parametrized by a first-order theory on the considered data domain. We show that our framework is suitable for reasoning about various classes of systems such as recursive sequential programs, multithreaded programs, parametrized and dynamic networks of processes, etc. Then, we provide generic results (1) for the decidability of the satisfiability problem of the fragment $\exists^*\forall^*$ of this logic provided that the underlying logic on data is decidable, and (2) for proving inductive invariance and for carrying out Hoare style reasoning within this fragment. We also show that the reachability problem is decidable for a class of prefix rewriting systems with integer data.

    Oscar H. Ibarra (Santa Barbara, CA, USA)
    Spiking Neural P Systems: Some Characterizations (with S. Woodworth)

      We look at the recently introduced neural-like systems, called SN P systems. These systems incorporate the ideas of spiking neurons into membrane computing. We study various classes and characterize their computing power and complexity. In particular, we analyze asynchronous and sequential SN P systems and present some conditions under which they become (non-)universal. The non-universal variants are characterized by monotonic counter machines and partially blind counter machines and, hence, have many decidable properties. We also investigate the language-generating capability of SN P systems.

    László Lovász (Budapest, Hungary)
    Approximating graphs by graphs and functions

      In many areas of science huge networks (graphs) are central objects of study: the internet, the brain, various social networks, VLSI, statistical physics. To study these graphs, new paradigms are needed: What are meaningful questions to ask? When are two huge graphs "similar"? How to "scale down" these graphs without changing their fundamental structure and algorithmic properties? How to generate random examples with the desired properties? A reasonably complete answer can be given in the case when the huge graphs are dense (in the more difficult case of sparse graphs there are only partial results).

    Philip Scott (Ottawa, Canada)
    Traces, Feedback, and the Geometry of Computation

      In the late '80s and early '90s, an algebraic structure dealing with cyclic operations emerged from various fields, including flowchart schemes, dataflow with feedback, action calculi in concurrency theory, proof theory (Geometry of Interaction), and network algebra, as well as in pure mathematics. This structure, now known as a "traced monoidal category", was formally introduced in an influential paper of Joyal, Street and Verity (1996) arising from work in topology and knot theory. However, these authors were also keenly aware of its potential applicability. Since then, these structures have been used, with variations, in several areas of mathematics, logic and theoretical computer science, including recent work in quantum computation and quantum protocols. We shall survey applications in logic, proof theory, and computability theory and discuss progress towards an abstract geometry of algorithms.