CSL and MFCS'98 - Preliminary Programme Schedule

(Still subject to changes and/or updates)




Last Update August 21, 1998




Saturday
August 22
Satellite Workshops
  • MFCS'98 Workshop on Grammar Systems
    • (10:00 - 10:10) Opening
    • (10:10 - 12:10) Session: Grammar systems I. Chair: Gheorghe Paun
      • (10:10 - 10:50)
        Erzsébet Csuhaj-Varjú (Budapest)
        Networks of Language Processors

      • (11:00 - 11:20)
        Tudor Balanescu, Horia Georgescu, Marian Gheorghe (Bucurest)
        Grammatical Models for Some Process Synchonizers

      • (11:25 - 11:45)
        Sebastian Maneth
        Cooperating Distributed Hyperedge Replacement Grammars

      • (11:50 - 12:10)
        György Vaszil (Budapest)
        Communication in Parallel Communicating Lindenmayer Systems

    • (14:00 - 15:35) Session: Colonies. Chair: Detlef Wotschke
      • (14:00 - 14:40)
        Carlos Martin-Vide (Tarragona),
        Gheorghe Paun(Bucharest)
        New Topics in Colonies Theory

      • (14:50 - 15:10)
        Jozef Kelemen (Opava/Bratislava)
        Colonies - A Theory of Reactive Agents

      • (15:15 - 15:35)
        Ján Gaso (Bratislava)
        Unreliable Colonies and Systems of Stochastic Grammars

    • (15:55 - 17:05) Chair: Rudolf Freund
      • (15:55 - 16:35)
        Victor Mitrana (Bucharest)
        Cooperation in Contextual Grammars

      • (16:45 - 17:05)
        Erzsébet Csuhaj-Varjú (Budapest),
        Maria D. Jiménez-López (Tarragona)
        Cultural Eco Grammar Systems: A Multi-Agent System for Cultural Change





Sunday
August 23
Tutorials:
  • (10:00 - 13:00, 14:30 - 17:30) Chair: I. Guessarian
    E. Boerger (Pisa) and Yu. Gurevich (Ann Arbor)
    Abstract state machines

  • (10:00 - 13:00, 14:30 - 17:30) Chair: P. Voda
    B. Buchberger (RISC - Linz) and T. Jebelan (RISC - Linz)
    The Theorema system: An introduction with demos

  • (14:00 - 16:00)
    Lev Beklemishev (Steklov Mathematical Institute, Moscow)
    Inference Rules in Fragments of Arithmetic

  • (16:30 - 18:30)
    Greg Morrisett (Cornell University, USA)
    Proofs, Types, and Safe Mobile Code
Satellite Workshops
  • MFCS'98 Workshop on Grammar Systems
    • (9:00 - 10:10) Session: Eco-Grammar Systems. Chair: Erzsébet Csuhaj-Varjú
      • (9:00 - 9:40)
        Alica Kelemenová (Opava)
        Descriptional Complexity Aspects in Colonies and Eco Grammar

      • (9:50 - 10:10)
        Judit Csima (Budapest)
        On Hybrid Eco-rewriting Systems

    • (10:30 - 12:00) Chair: Victor Mitrana
      • (10:30 - 10:50)
        Petr Sosík (Opava)
        Eco Grammar Systems, Decidability and the Tiling Problem

      • (10:55 - 11:25)
        Blanca Cases (San Sebastián)
        Computing Linear Systems of First Order Equations on Integers and Naturals by Simple Ecogrammars

      • (11:30 - 12:00)
        Radim Petr, Alica Kelemenová (Opava)
        On Deterministic Ecogrammar Systems

    • (14:00 - 15:35) Session: Grammar systems II. Chair: Jozef Kelemen
      • (14:00 - 14:40)
        Rudolf Freund (Vienna)
        Array Grammar Systems

      • (14:50 - 15:10)
        Cyrus F. Nouran (Santa Barbara)
        Intelligent Languages. A Preliminary Syntatic Theory

      • (15:15 - 15:35)
        Christos Orovas, James Austin (York)
        Cellular Associative Symbolic Processing for Pattern Recognition





Monday
August 24
(8:15 - 8:30) Opening

Invited Talks Chair: A. Salomaa
  • (8:30 - 9:30)
    Yu. Matiyasevich (Petersburg)
    Trace Monoids and their Decision Problems

  • (9:30 - 10:30)
    R.M. Karp (Seattle)
    Algorithms for Mapping and Sequencing the Human Genome

  • (11:00 - 12:00)
    A. Pnueli (Rehovot)
    Modularization and Abstraction: The Keys to Practical Formal Verification
Session A1: Complexity of Hard problems (14:00 - 16:00) Chair: P. Pudlak
  • (14:00 - 14:30)
    Michael Alekhnovich, Sam Buss, Shlomo Moran, Toniann Pitassi
    Minimum Propositional Proof Length is NP-Hard to Linearly Approximate

  • (14:30 - 15:00)
    Nikolai N. Kuzjurin
    Locally explicit construction of Rodl's asymptotically good packings

  • (15:00 - 15:30)
    Mikel Aldaz, Joos Heintz, Guillermo Matera, Jose L. Montana, Luis M. Pardo
    Combinatorial Hardness Proofs for Polynomial Evaluation

  • (15:30 - 16:00)
    Marek Chrobak, Christoph Durr
    Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms

Session B1: Logic - Semantics - Automata (14:00 - 16:00) Chair: B. Trachtenbrot
  • (14:00 - 14:30)
    Flemming Nielson, Hanne Riis Nielson
    Flow Logic for Imperative Objects

  • (14:30 - 15:00)
    Alexander Rabinovich
    Expressive Completeness of Temporal Logic of Action

  • (15:00 - 15:30)
    Matthias Baaz, Agata Ciabattoni, Christian Fermueller, Helmut Veith
    Proof Theory of Fuzzy Logics: Urquhart's C and Related Logics

  • (15:30 - 16:00)
    Richard Bonner, Rusins Freivalds, Janis Lapins, Antra Lukjanska
    Nonstochastic languages being projections of 2-tape quasideterministic languages
Session C1 (CSL): Logic Programming and Quantifiers (14:00 - 16:00)
  • (14:00 - 14:30)
    D. Kempe, A. Schoenegge
    On the power of quantifiers in first-order algebraic specification

  • (14:30 - 15:00)
    F. Giannotti, G. Manco, M. Nanni, D. Pedreschi
    On The Effective Semantics of Nondeterministic, Nonmonotonic, Temporal Logic Databases

  • (15:00 - 15:30)
    V. Marek, I. Pivkina, M. Truszczynski
    Revision programming = logic programming + constraints

  • (15:30 - 16:00)
    U. Egly
    Quantifiers and the System KE: Some Surprising Results
Session A2: Rewriting (16:30 - 18:30) Chair: A. Arnold
  • (16:30 - 17:00)
    H. Touzet
    Encoding the Hydra Battle as a rewrite system

  • (17:00 - 17:30)
    Zoltan Fulop, Eija Jurvanen, Magnus Steinby, Sandor Vagvolgyi
    On One-pass Term Rewriting

  • (17:30 - 18:00)
    Maria Ferreira, Delia Kesner, Laurence Puel
    Reducing AC-Termination to Termination

  • (18:00 - 18:30)
    Miki Hermann, Gernot Salzer
    On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations
Session B2: Automata and Transducers (16:30 - 18:30) Chair: J. Karhumaki
  • (16:30 - 17:00)
    Holger Petersen
    The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses

  • (17:00 - 17:30)
    Christian Hagenah, Anca Muscholl
    Computing epsilon-Free NFA from Regular Expressions in O(n log^2(n)) Time

  • (17:30 - 18:00)
    Michel Latteux, David Simplot, Alain Terlutte
    Iterated Length-Preserving Transductions

  • (18:00 - 18:30)
    Geraud Senizergues
    The equivalence problem for deterministic pushdown transducers into abelian groups
Session C2 (CSL): Finite Model Theory (16:30 - 18:30)
  • (16:30 - 17:00)
    H.K. Hoang
    Choice Construct and Lindstrom logics

  • (17:00 - 17:30)
    M. Kreidler, D. Seese
    Monadic NP and Graph Minors

  • (17:30 - 18:00)
    J.A. Makowsky
    Invariant definability and P/poly

  • (18:00 - 18:30)
    E. Pezzoli
    Computational Complexity of Ehrenfeucht-Fraisse games on finite structures
Satellite Workshops
  • CCA'98 - Workshop on Computability and Complexity in Analysis
    • (14:00 - 16:00)
      • (14:00 - 14:40)
        Armin Hemmerling
        On the time complexity of partial real functions

      • (14:40 - 15:20)
        Henri-Alex Esbelin
        Rudimentary computable reals

      • (15:20 - 16:00)
        Marian Pour-El
        Some open problems in computable analysis

    • (16:30 - 18:30)
      • (16:30 - 17:10)
        Kamo Hiroyasu, Kawamura Kiko, Takeuti Izumi
        Hausdorff dimension and computational complexity

      • (17:10 - 17:50)
        Mariko Yasugi, Masako Washihara
        Computability problem of gaussian function

      • (17:50 - 18:30)
        Holger Schulz
        Type two theory of effectivity an Real PCF


  • Frontiers between Decidability and Undecidability
    • (14:00 - 16:00) Chair: M. Margenstern
      • (14:00 - 14:30)
        R. Freund, H. Fernau, M. Holzer
        Representations of recursively enumerable array languages by d-dimensionnal contextual array grammars

      • (14:30 - 15:00)
        H. Petersen
        Universality of Baxter Machines

      • (15:00 - 15:30)
        M. Kudlek
        On Universal Finite Automata and a-Transducers

      • (15:30 - 16:00)
        J.H. Nixon
        Ideas for describing the behaviour of small Turing machines with complex behaviour

    • (16:30 - 18:00) Chair: R. Freund
      • (16:30 - 17:30) Invited Talk:
        L. Kari (London, Ontario)
        Achieving Universal Computational Power Using DNA

      • (17:30 - 18:00)
        V.A. Zakharov
        On the decidability of the equivalence problem for monadic recursive programs


  • MFCS'98 Workshop on Communications
    • (14:00 - 16:00) Chair: J. Hromkovic
      • (14:00 - 14:30)
        G. Fertin, J.G. Peters
        Odd gossiping in the linear cost model

      • (14:30 - 15:00)
        L. Barriere, J. Cohen, M. Mitjana
        Gossipping in Chordal Rings under the Line Model

      • (15:00 - 16:00) Invited Talk:
        Ralf Klasing
        Methods and problems of wavelength routing in all-optical networks


    • (16:30 - 18:00) MFCS'98 papers. Chair: R. Klasing
      • (16:30 - 17:00)
        J. Hromkovic
        Communication complexity and Lower Bounds on Multilective Computations

      • (17:00 - 17:30)
        C. Damm
        On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols

      • (17:30 - 18:00)
        V. Auletta, I. Caragiannis, C. Kaklamanis, P. Persiano
        On the Complexity of Wavelength Converters


  • Molecular Computing
    • (14:00 - 16:00) Chair: G. Paun
      • (14:00 - 15:00) Invited Talk:
        J. Reif (Duke University)
        Experiments in Biomolecular Computation

      • (15:00 - 15:30)
        G. Ciobanu
        On a Formal Decomposition of the Molecular Interaction

      • (15:30 - 16:00)
        E. Csuhaj-Varju
        Watson-Crick Reactive Systems

    • (16:30 - 19:00) Chair: L. Kari
      • (16:30 - 17:00)
        F. Freund, R. Freund
        Computations on Double-Stranded Molecules

      • (17:00 - 17:30)
        M. Christersson
        DNA Computation of Integer Addition Table with Applications to Boolean Convolution

      • (17:30 - 18:00)
        J. Castellanos, J. Rodrigo, A. Rodriguez-Paton
        Evolutionary Biomolecular Computing

      • (18:00 - 18:30)
        V. Manca
        Logical Rewriting and Molecular Computing

      • (18:30 - 19:00)
        M. Ogihara, A. Ray
        Evaluation of Boolean Circuits by Primary Extension on DNA Templates




Tuesday
August 25
Invited Talks Chair: S. Abramsky
  • (8:30 - 9:30)
    M. Yannakakis (Murray Hill)
    Testing of Finite State Systems

  • (9:30 - 10:30)
    Yu. Gurevich (Ann Arbor)
    Logic with Choice

  • (11:00 - 12:00)
    P. Pudlak (Prague)
    On Algorithms for Satisfiability

  • (14:00 - 15:00)
    Th. Schwentick
    Descriptive Complexity and Lower Bounds
Session A1: Typing (14:00 - 16:00) Chair: Z. Esik
  • (14:00 - 14:30)
    Gilles Barthe
    The semi-full closure of Pure Type Systems

  • (14:30 - 15:00)
    Marcin Benke
    Predicative Polymorphic Subtyping

  • (15:00 - 15:30)
    G.M. Bierman
    A Computational Interpretation of the lambdamu-calculus

  • (15:30 - 16:00)
    Jacek Chrzaszcz
    Polymorhic subtyping without distributivity
Session B1: Concurrency - Semantics - Logic (14:00 - 16:00) Chair: J. Esparza
  • (14:00 - 14:30)
    Thomas Hune, Mogens Nielsen
    Timed Bisimulation and Open Maps

  • (14:30 - 15:00)
    Jiri Srba
    Deadlocking States in Context-free Process Algebra

  • (15:00 - 15:30)
    Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari
    Complete Abstract Interpretations made Constructive

  • (15:30 - 16:00)
    Paul Gastin, Raphael Meyer, Antoine Petit
    A (non-elementary) modular decision procedure for LTrL
Session C1 (CSL): Propositional Proofs and Satisfiability (15:00 - 16:00)
  • (15:00 - 15:30)
    H. Kleine Buening
    An Upper Bound for Minimal Resolution Refutations

  • (15:30 - 16:00)
    Z. Sadowski
    On an optimal deterministic algorithm for SAT
Session A2: Circuit Complexity (16:30 - 18:30) Chair: J. Sgall
  • (16:30 - 17:00)
    Lane A. Hemaspaandra, Joerg Rothe
    A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem

  • (17:00 - 17:30)
    Andris Ambainis, David Mix Barrington, Huong LeThanh
    On counting AC^0 circuits with negative constants

  • (17:30 - 18:00)
    Kazuyuki Amano, Akira Maruoka
    A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)loglog n Negation Gates

Session B2: Programming (16:30 - 18:30) Chair: E. Boerger
  • (16:30 - 17:00)
    Alessandra Di Pierro, Herbert Wiklicky
    Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Model

  • (17:00 - 17:30)
    E. Allen Emerson, Richard J. Trefler
    Model Checking Real-Time Properties of Symmetric Systems

  • (17:30 - 18:00)
    Alex K. Simpson
    Lazy Functional Algorithms for Exact Real Functionals

  • (18:00 - 18:30)
    Martin Grohe, Thomas Schwentick
    Locality of order-invariant first-order formulas
Session C2 (CSL): Complexity, Logic and Programming (16:30 - 18:00)
  • (16:30 - 17:00)
    M. Korovina, O. Kudinov
    Characteristic Properties of Majorant-Computability over the Reals

  • (17:00 - 17:30)
    J. Komara, P.J. Voda
    Theorems of Peter and Parsons in Computer Programming

  • (17:30 - 18:00)
    J. Riche, R.K. Meyer
    Kripke, Belnap, Urquhart and Relevant Decidability and Complexity
EACSL Membership Meeting (18:30 - 19:30)

Satellite Workshops
  • CCA'98 - Workshop on Computability and Complexity in Analysis
    • (14:00 - 16:00)
      • (14:00 - 14:40)
        Hideki Tsuiki
        Gray code representation of exact real numbers

      • (14:40 - 15:20)
        Douglas Bridges
        Bishop's principle

      • (15:20 - 16:00)
        Klaus Weihrauch, Ning Zhong
        The wave propagator is computable

    • (16:30 - 18:30)
      • (16:30 - 17:10)
        Vasco Brattka
        A stability theorem for recursive analysis

      • (17:10 - 17:50)
        Matthias Schroeder
        Effective metrization of regular spaces

      • (17:50 - 18:30) MFCS'98 talk:
        Klaus Weihrauch, Xizhong Zheng (Duke University)
        A finite hierarchy of the recursively enumerable real numbers


  • Frontiers between Decidability and Undecidability
    • (14:00 - 16:00) Chair: S. Grigorieff
      • (14:00 - 14:30)
        M. Hirvensalo
        Copying quantum computer makes NP-complete problems tractable

      • (14:30 - 15:00)
        B. Martin
        Simulation results for spatial machines

      • (15:00 - 15:30)
        M. Margenstern, Yu. Rogojine
        Time-varying distributed H-systems of degree 2 generate any r.e. language

      • (15:30 - 16:00)
        K. Morita, M. Margenstern, K. Imai
        Universal reversibal hexagonal cellular automata

    • (16:30 - 17:30) Chair: K. Morita
      • (16:30 - 17:30) Invited Talk:
        S. Grigorieff (Paris)
        Decidability/Undecidability problems for multi-tape finite automata

  • MFCS'98 Workshop on Cellular Automata
    • (14:00 - 16:00) Chair: T. Worsch
      • (14:00 - 14:30)
        G. Manzini
        Characterization of Sensitive Linear Cellular Automata with Respect to the Counting Distance

      • (14:30 - 15:00)
        G. Cattane, L. Margara
        Topological Definitions of Chaos applied to Cellular Automata Dynamics

      • (15:00 - 15:30)
        I. Rapaport, J. Mazoyer
        Additive Cellular Automata over {Z}_p and the Bottom of (CA,leq)

      • (15:30 - 16:00)
        T. Buchholz, A. Klein, M. Kutrib
        One guess one-way cellular arrays

    • (16:30 - 18:00) Chair: K. Kobayashi
      • (16:30 - 17:00)
        H. Umeo
        Cellular Algorithms with 1-bit Inter-Cell Communications (invited paper)

      • (17:00 - 17:30)
        B. Martin
        A Geometrical Hierarchy of Graph via Cellular Automata

      • (17:30 - 18:00)
        C. Nichitiu, E. Rémila
        Simulations of graph automata


  • MFCS'98 Workshop on Communications
    • (14:00 - 18:00) Chair: W. Unger
      • (14:00 - 14:30)
        N. Deo , B. Litow
        A Structural Approach to Graph Compression

      • (14:30 - 15:00)
        S.A. Jassim and J.M.R. Martin
        Graph Techniques for Deadlock Analysis of Process Networks

      • (15:00 - 15:30)
        P.K.W. Cheng, F.C.M. Lau, S.S.H. Tse
        An Algorithm for the Location Problem in Two-Dimensional Meshes

      • (15:30 - 16:00)
        H. Bockenhauer
        Two open problems in communication in edge-disjoint paths mode

      • (16:30 - 17:00)
        C. Padro, G. Saez
        Lower Bounds on the Information Rate of Secret Sharing Schemes with Homogenoues Access Structure

      • (17:00 - 17:30)
        E. Jennings
        Finding Central Paths in Networks

      • (17:30 - 18:00)
        A. Goerdt
        Random regular graphs with edge faults --- expansion through cores

  • Molecular Computing
    • (14:00 - 16:00) Chair: J. Reif
      • (14:00 - 15:00) Invited Talk:
        Lila Kari (London, Ontario)
        Towards a DNA solution to the Shortest Common Superstring Problem

      • (15:00 - 15:30)
        J. Dassow
        Mutations in Genomes and Operations on Formal Languages

      • (15:30 - 16:00)
        S. Bozapalidis, G. Rahonis
        H Tree Schemes with Finite Sets of Rules

    • (16:30 - 18:30) Chair: J. Dassow
      • (16:30 - 17:00)
        P. Bonizzoni, C. Ferretti, G. Mauri
        Splicing Systems with Marked Rules

      • (17:00 - 17:30)
        Y. Sakakibara, S. Kobayashi
        Parsing with Splicing Systems

      • (17:30 - 18:00)
        V.T. Chakavarthy, K. Krithivasan
        Some Results on Simple Extended H Systems

      • (18:00 - 18:30)
        V. Mitrana
        On the Duplication Grammars




Wednesday
August 26
Invited Talks Chair: R. Karp
  • (8:30 - 9:30)
    W. Maass (Graz)
    On the Role of Time and Space in Neural Computations

  • (9:30 - 10:30)
    J. Wiedermann (Prague)
    Towards Algorithmic Explanation of Mind Evolution and Functioning

  • (9:30 - 10:30)
    I. Nemeti
    Connections between Temporal Logics of Programs (Actions), Temporal Logics of Relativity Theory and Logic of Relativity
    THE TALK CANNOT BE DELIVERED DUE TO UNEXPECTED PERSONAL PROBLEMS OF THE AUTHOR

  • (11:00 - 12:00)
    E. Boerger (Pisa)
    Mathematical Analysis of Java programs

  • (11:00 - 12:00)
    P. Hajek (Prague)
    Trakhtenbrot's Theorem and Fuzzy Logic



Thursday
August 27
Invited Talks Chair: A. Pnueli
  • (8:30 - 9:30)
    S. Micali (MIT-Cambridge)
    Computationally-Sound Proofs and Checkers

  • (9:30 - 10:30)
    G. Ausiello (Rome)
    Dynamic Algorithms for Directed Hypergraphs and Applications

  • (9:30 - 10:30)
    J. Mitchell
    Analysis of security protocols

  • (11:00 - 12:00)
    M. Nielsen (Aarhus)
    Reasoning about the Past

Session A1: Structural Complexity (14:00 - 16:00) Chair: P. van Emde Boas
  • (14:00 - 14:30)
    Johannes Koebler, Rainer Schuler
    Average-Case Intractability vs. Worst-Case Intractability

  • (14:30 - 15:00)
    Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt
    Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets

  • (15:00 - 15:30)
    Levke Bentzien
    Positive Turing and Truth-Table Completeness for NEXP Are Incomparable

  • (15:30 - 16:00)
    Judy Goldsmith, Mitsunori Ogihara, Joerg Rothe
    Tally NP Sets and Easy Census Functions
Session B1: Formal Languages (14:00 - 16:00) Chair: C. Choffrut
  • (14:00 - 14:30)
    Tero Harju, Alexandru Mateescu, Arto Salomaa
    Shuffle on trajectories: a simplified approach to the Schutzenberger product and related operations

  • (14:30 - 15:00)
    Isabelle Ryl, Yves Roos, Mireille Clerbout
    About Synchronization Languages

  • (15:00 - 15:30)
    Luis-Miguel Lopez, Philippe Narbel
    D0L-Systems and Surface Automorphisms

  • (15:30 - 16:00)
    Werner Kuich
    Gaussian elimination and a characterization of algebraic power series
Session C1 (CSL): Lambda-Calculus and Types (14:00 - 16:00)
  • (14:00 - 14:30)
    G. Barthe
    Existence and uniqueness of normal forms in pure type systems with beta-eta conversion

  • (14:30 - 15:00)
    Z. Khasidashvili, A. Piperno
    Normalization of Typable Terms by Superdevelopments

  • (15:00 - 15:30)
    S. Vorobyov
    Subtyping Functional+Nonempty Record Types

  • (15:30 - 16:00)
    R. Matthes
    Monotone Fixed-Point Types And Strong Normalization
Session A2: Graphs and Hypergraphs (16:30 - 18:30) Chair: J. Opatrny
  • (16:30 - 17:00)
    Thomas Hofmeister,Hanno Lefmann
    Approximating Maximum Independent Sets in Uniform Hypergraphs

  • (17:00 - 17:30)
    Salvatore La Torre, Margherita Napoli
    Representing Hyper-Graphs by Regular Languages

  • (17:30 - 18:00)
    Klaus Barthelmann
    When Can an Equational Simple Graph Be Generated by Hyperedge Replacement?

  • (18:00 - 18:30)
    M. Grosse-Rhode, F. Parisi-Presicce, M. Simeoni
    Spatial and Temporal Refinement of Typed Graph Transformation Systems
Session B2: Turing Complexity - Logic (16:30 - 18:30) Chair: W. Brauer
  • (16:30 - 17:00)
    Jiri Wiedermann
    Speeding-up Nondeterministic Single-Tape Off-Line Computations by One Alterantion

  • (17:00 - 17:30)
    Kazuo Iwama, Chuzo Iwamoto
    Improved Time and Space Hierarchies of One-Tape Off-Line TMs

  • (17:30 - 18:00)
    Pawel Mielniczuk, Leszek Pacholski
    Tarskian set constraints are in NEXPTIME

  • (18:00 - 18:30)
    Sergei Vorobyov
    forallexists^ast-Equational Theory of Context Unification is Pi_1^0-Hard

Session C2 (CSL): Categories and Lambda-Calculus (16:30 - 18:00)
  • (16:30 - 17:00)
    R. Statman
    Morphisms and Partitions of V-sets

  • (17:00 - 17:30)
    A. K. Simpson
    Computational Adequacy in an Elementary Topos

  • (17:30 - 18:00)
    Th. Altenkirch
    Logical relations and inductive/coinductive types

Satellite Workshops
  • CCA'98 - Workshop on Computability and Complexity in Analysis
    • (14:00 - 15:20)
      • (14:00 - 14:40)
        John Tucker, Jeff Zucker
        Infinitary algebraic specifications for stream algebras

      • (14:40 - 15:20)
        Andre Lieutier
        Toward a data type for solid modeling based on domain theory


  • FICS'98 - Fixed Points in Computer Science
    • (14:00 - 16:00) Chair: Z. Esik
      • (14:00 - 15:00) Invited Talk:
        Y.N. Moschovakis (Amsterdam)
        Higher type concurrent recursion

      • (15:00 - 15:30):
        J.J.M.M. Rutten
        Fixed points and final coalgebras

      • (15:30 - 16:00):
        A. Corradini, F. Gadducci
        Rewriting on cyclic structures

    • (16:30 - 18:30) Chair: I. Guessarian
      • (16:30 - 17:30) Invited Talk:
        J.W. de Bakker (Amsterdam)
        Fixed points in metric semantics

      • (17:30 - 18:00):
        R. Backhouse
        Fixed points and generic programming, Part I

      • (18:00 - 18:30):
        J.M. Davoren
        Topologies, continuity and bisimulations

  • Randomized Algorithms
    • (14:00 - 16:00) Chair: Rusins Freivalds
      • (14:00 - 14:30)
        Richard Bonner
        Randomization of positive linear learning algorithms in Banach function lattices

      • (14:30 - 15:00)
        Eric Allender, Shiyu Zhou
        Uniform inclusions in nondeterministic logspace

      • (15:00 - 16:00) Invited Talk:
        M. Karpinski
        On the Computational Power of Randomized Branching Programs

    • (16:30 - 18:00) Chair: G. Brassard
      • (16:30 - 17:00)
        Farid Ablayev, Marek Karpinski, Rustam Mubarakzjanov
        On BPP versus NP v coNP for ordered read-once branching programs

      • (17:00 - 17:30)
        Dainis Geidmanis, Janis Kaneps, Tomas Larfeldt
        Single-letter languages accepted by alternating and probabilistic pushdown automata

      • (17:30 - 18:00)
        Anssi Kautonen, Ville Leppanen, Martti Penttonen
        Thinning protocols for routing h-relations in complete networks
      • (18:00 - 18:30)
        Boris D. Lubachevsky
        Why hard disks pack easier



  • Mathematical Linguistics

    • (14:00 - 16:00) Chair: Manfred Kudlek
      • (14:00 - 15:00) Invited Talk:
        Solomon Marcus
        Contextual Grammars, Learning Processes and the Kolmogorov-Chaitin Metaphor

      • (15:00 - 15:30)
        E. Csuhaj-Varju, M.D. Jimenez-Lopez, C. Martin-Vide
        Pragmatic Eco-Rewriting Systems : A Model of Conversations in Terms of Formal Grammars

      • (15:30 - 16:00)
        P. Jancar, F. Mraz, M. Platek, J. Vogel
        On Monotony for Restarting Automata

    • (16:30 - 18:30) Chair: Solomon Marcus
      • (16:30 - 17:00)
        M. Kudlek, A. Mateescu
        Distributed Catenation : An Overview

      • (17:00 - 17:30)
        M. Novotny
        Reduction of Pregrammars

      • (17:30 - 18:00)
        C. Martin-Vide, V. Mitrana
        An Algebraic Model of Synonomy

      • (18:00 - 18:30)
        P. Martinek
        Limits of Pure Grammars with Monotone Productions


  • MFCS'98 Workshop on Cellular Automata
    • (14:00 - 16:00) Chair: K. Morita
      • (14:00 - 14:30)
        K. Sutner
        Computation Theory of Cellular Automata (invited paper)

      • (14:30 - 15:00)
        K. Kobayashi
        On Time Optimal Solutions of the Two-Dimensional Firing Squad Synchronization Problem

      • (15:00 - 15:30)
        F. Reischle, Th. Worsch
        Simulations between alternating CA, alternating TM and circuit families

      • (15:30 - 16:00)
        K. Svozil
        Is the world a machine? (invited paper)

    • (16:30 - 18:00) Chair: G. Mauri
      • (16:30 - 17:00)
        K. Morita
        Number-Conserving Reversible Cellular Automata and Their Computation-Universality (invited paper)

      • (17:00 - 17:30)
        L. Margara
        Topological Mixing and Denseness of Periodic Orbits for Linear Cellular Automata over Z_m

      • (17:30 - 18:00)
        E. Formenti
        Cellular automata in the Cantor, Besicovitch and Weyl Spaces (invited paper)


  • MFCS'98 Workshop on Concurrency
    • (14:00 - 16:00) Chair: Javier Esparza
      • (14:00 - 14:30)
        R. De Nicola, A. Labella
        The Morphisms and Bisimulations

      • (14:30 - 15:00)
        D. Hirschkoff
        Automatically Proving Up-to Bisimulation

      • (15:00 - 15:30)
        G. Ciobanu, M. Rotaru
        A Faithful Graphical Representation of the pi-calculus: Faithful pi-nets

      • (15:30 - 16:00)
        O. Kushnarenko, S. Pinchinat
        Intentional Approaches for Symbolic Methods


    • (16:30 - 18:30) Chair: Colin Stirling
      • (16:30 - 17:00)
        A. Maggiolo-Schettini, S. Tini
        Projectable Semantics for Statecharts

      • (17:00 - 17:30)
        I. Virbitskaite
        On the Semantics of Concurrency and Nondeterminism: Bisimulations and Temporal Logics

      • (17:30 - 18:30) Invited Talk:
        Javier Esparza, Munich
        Unfoldings: verification using partial orders





Friday
August 28
Invited Talks Chair: G. Ausiello
  • (8:30 - 9:30)
    D. Harel (Rehovot)
    Towards a Theory of Infinite Recursive Structures and Databases

  • (9:30 - 10:30)
    C. Stirling (Edinburgh)
    The Joys of Bisimulation

  • (11:00 - 12:00)
    K. Mehlhorn (Saarbrucken)
    From Algorithm to Program

  • (11:00 - 12:00)
    J. Tiuryn
    Can we Make Subtyping over a Lattice of Atomic Types Practically Feasible?

Session A1: OBDD (14:00 - 16:00) Chair: D. Pardubska
  • (14:00 - 14:30)
    Kazuo Iwama, Mitsushi Nozoe
    Optimizing OBDDs Is Still Intractable for Monotone Functions

  • (14:30 - 15:00)
    Anna Slobodova
    On the Composition Problem for OBDDs With Different Variable Orderings

  • (15:00 - 15:30)
    Harry Preuss, Anand Srivastav
    Blockwise Variable Orderings for Shared BDDs

  • (15:30 - 16:00)
    Bruno Courcelle, Denis Lapoire
    Facial circuits of planar graphs and context-free languages
Session B1: Combinatorics on Words (14:00 - 16:00) Chair: W. Kuich
  • (14:00 - 14:30)
    Roman Kolpakov, Gregory Kucherov, Yuri Tarannikov
    On repetition-free binary words of minimal density

  • (14:30 - 15:00)
    Juhani Karhumaeki, Jan Manuch, Wojciech Plandowski
    On defect effect of bi-infinite words

  • (15:00 - 15:30)
    Christian Choffrut, Sandor Horvath
    Equations in transfinite strings

  • (15:30 - 16:00)
    M. Crochemore, F. Mignosi, A. Restivo
    Minimal forbidden words and factor automata

Session C1 (CSL): Theorem Proving and Complexity (14:00 - 16:00)
  • (14:00 - 14:30)
    R. Pichler
    On the Complexity of H-Subsumption

  • (14:30 - 15:00)
    J. Levy, M. Veanes
    On Unification Problems in Restricted Second-Order Languages

  • (15:00 - 15:30)
    G. Bonfante, A. Cichon, JY. Marion, H. Touzet
    Complexity classes and rewrite systems with polynomial interpretation

  • (15:30 - 16:00)
    P. Narendran, M. Rusinowitch, R. Verma
    RPO constraint solving is in NP

Session A2: Trees and Embeddings (16:30 - 18:30) Chair: K. Mehlhorn
  • (16:30 - 17:00)
    Sergej Bezrukov, Joe Chavez, Larry Harper, Markus Roettger, Ulf-Peter Schroeder
    Embedding of Hypercubes into Grids

  • (17:00 - 17:30)
    Hajo Broersma, Andreas Huck, Ton Kloks, Otto Koppius, Dieter Kratsch, Haiko Mueller, Hilde Tuinstra
    Degree-preserving forests

  • (17:30 - 18:00)
    A. Crauser, K. Mehlhorn, U. Meyer, P. Sanders
    A Parallelization of Dijkstra's Shortest Path Algorithm

  • (18:00 - 18:30)
    Hans L. Bodlaender, Torben Hagerup
    Tree decompositions of small diameter
Session B2: Picture Languages - Function Systems/Complexity (16:30 - 18:30) Chair: W. Thomas
  • (16:30 - 17:00)
    Klaus Reinhardt
    On some recognizable picture-languages

  • (17:00 - 17:30)
    Oliver Matz
    One Quantifier Will Do in Existential Monadic Second-Order Logic over Pictures

  • (17:30 - 18:00)
    Henning Fernau, Ludwig Staiger
    Iterated Function Systems and Control Languages

  • (18:00 - 18:30)
    Bruno Durand, Sylvain Porrot
    Comparison between the complexity of a function and the complexity of its graph
Session C2 (CSL): Fuzzy and Multivalued Logics (16:30 - 18:00)
  • (16:30 - 17:00)
    O. Arieli, A. Avron
    Using Four Values for Computerized Reasoning

  • (17:00 - 17:30)
    M. Baaz, H. Veith
    Quantifier Elimination in Fuzzy Logic

  • (17:30 - 18:00)
    Th. Lukasiewicz
    Many-valued First-order Logics with Probabilistic Semantics
Satellite Workshops
  • FICS'98 - Fixed Points in Computer Science
    • (14:00 - 16:00) Chair: S.L. Bloom
      • (14:00 - 14:30):
        R. Backhouse, P. Hoogendijk
        Fixed points and generic programming, Part II

      • (14:30 - 15:00):
        G. Plotkin, A.K. Simpson
        Properties of fixed points in axiomatic domain theory

      • (15:00 - 15:30):
        R. Matthes
        Monotone (co)inductive types and positive fixed point types

      • (15:30 - 16:00):
        R. Hasegawa
        The Lagrange-Good inversion as the trace of formal power series

    • (16:30 - 19:00) Chair: R. Backhouse
      • (16:30 - 17:30) Invited Talk:
        A. Arnold (Bordeaux)
        The boolean mu-calculus and its relations with model-checking and games

      • (17:30 - 18:00):
        J. Bradfield
        Fixpoint alternation on trees

      • (18:00 - 18:30) Invited Talk:
        H. Seidl, D. Niwinski
        On fixpoint expressions with distributive operators

      • (18:30 - 19:00):
        R. Wastl
        A generalization of Van Gelder's alternating computing paradigm

  • Randomized Algorithms
    • (14:00 - 15:30) Chair: Marek Karpinski
      • (14:00 - 15:00) Invited Talk:
        G. Brassard (Montreal)
        The security of quantum bit commitment schemes

      • (15:00 - 15:30)
        Bruce Litow, Olivier de Vel
        On digital images which cannot be generated by small generalized stochastic automata

    • (16:00 - 18:00) Chair: E. Allender
      • (16:00 - 17:00) Invited Talk:
        A. Ambainis (Berkeley)
        Randomization in learning theory

      • (17:00 - 17:30)
        Michele Mosca
        Quantum searching, counting and amplitude amplification by eigenvector analysis

      • (17:30 - 18:00)
        Marius Zimand
        Efficient privatization of random bits


  • Mathematical Linguistics
    • (14:00 - 16:00) Chair: E. Csuhaj-Varju
      • (14:00 - 14:30)
        T. Becker
        Automaton Models for Weakly Context-sensitive Formalisms

      • (14:30 - 15:00)
        H. Krieger
        Typed Feature Structures, Definite Equivalences, Greatest Model Semantics, and Nonmonotonicity

      • (15:00 - 15:30)
        V. Manca
        Logical Splicing in Natural Lannguages

      • (15:30 - 16:00)
        R. Grammatovici
        Contextual Multilanguages and Operational Automata

    • (16:30 - 18:00) Chair: M. Novotny
      • (16:30 - 17:00)
        P. Dunges
        Eventualities in Time

      • (17:00 - 17:30)
        R. Ceterchi
        Selection Mechanisms Between Strings and Contexts - an Equational Approach

      • (17:30 - 18:00)
        M. Kudlek
        A Model of Personal Pronouns

  • MFCS'98 Workshop on Concurrency
    • (14:00 - 16:00) Chair: Wilfried Brauer
      • (14:00 - 14:30)
        U. Nitsche
        Construction of an Abstract State-Space from a Partial-Order Representation of the Concrete One

      • (14:30 - 15:00)
        M. Muller-Olm
        Derivation of Characteristic Formulae

      • (15:00 - 16:00) Invited Talk:
        Faron Moller, Uppsala
        Pushdown Automata, Multiset Automata, and Petri Net


    • (16:30 - 18:30) Chair: Petr Jančar
      • (16:30 - 17:00)
        O. Burkart
        Queues as Processes

      • (17:00 - 17:30)
        R. Mayr
        Strict Lower Bounds for Model Checking BPA

      • (17:30 - 18:00)
        J. Stříbrná
        Hardness Results for Weak Bisimilarity of Simple Process Algebra

      • (18:00 - 18:30)
        P. Paczkowski
        Characterizing Bisimilarity of Value-passing Processes with Context-free Control


  • Weak Arithmetic
    • (14:00 - 16:00) Chair: Yu. Matiyasevich
      • (14:00 - 15:00)
        P. Cegielski, D. Richard, and M. Vsmirnov
        On additive prime number theory

      • (15:00 - 15:30)
        J. Marion and D. Leivant
        A characterization of alternating log time by ramified recurrence

      • (15:30 - 16:00)
        I. Korec
        Definability of addition and multiplication from some qudratic forms ax^2 + cy^2

    • (16:30 - 18:00) Chair: D. Richard
      • (16:30 - 17:00)
        A. Esbelin
        Closure properties of sub-LINSPACE classes

      • (17:00 - 17:30)
        L. Boasson, P. Cegielski, I. Guessarian, and Yu. Matiiassevitch
        Subsequence problem

      • (17:30 - 18:00)
        C. Choffrut, H. Pelibossian, and P. Simonnet
        Decission issues on functions realised by finite automata


Saturday
August 29
Tutorials
  • (8:30 - 11:30, 13:00 - 16:00) Chair: J. Gruska
    C.H. Bennett (IBM Watson, Yorktown Heights) and K. Svozil (Wien)
    Quantum logic and quantum computing

  • (8:30 - 11:30, 13:00 - 16:00) Chair: J. Hromkovic
    J. Diaz (Rome) and A. Marchetti-Spaccamela (Rome)
    Approximations algorithms
Satellite Workshops
  • FICS'98 - Fixed Points in Computer Science
    • (9:00 - 11:00) Chair: W. Kuich
      • (9:00 - 9:30):
        F. Corradini, R. De Nicola, A. Labella
        A finite axiomatization of nondeterministic regular expressions

      • (9:30 - 10:00):
        J. Bradfield, P. Stevens
        Observational mu-calculus

      • (10:00 - 10:30):
        D. Gurov, B. Kapron
        A note on negative tagging for least fixed-point formulae

      • (10:30 - 11:00):
        R.L. Crole
        Modelling FIX in recursive object calculi

  • MFCS'98 Workshop on Concurrency
    • (9:00 - 10:30) Chair: Faron Moller
      • (9:00 - 9:30)
        G. Juhas
        The Essence of Petri Nets and Transition Systems through Abelian Groups

      • (9:30 - 10:00)
        S. Haar
        Branching Processes of General S/T-Systems

      • (10:00 - 10:30)
        J. Lilius
        Efficient State Space Search for Time Petri Nets


    • (11:00 - 12:00) Chair: Mojmír Křetínský
      • (11:00 - 11:30)
        V. Janousek, T. Vojnar
        State Spaces of Object-Oriented Petri Nets

      • (11:30 - 12:00)
        I. V. Tarasyuk
        Place Bisimulation Equivalences for Design of Concurrent Systems

  • 68th Peripathetic Seminar on Sheaves and Logic

    • (9:00 - 12:30)
      • (9:00 - 9:30)
        P. T. Johnstone
        How bad can a category of sheaves be?

      • (9:40 - 10:10)
        J. Adamek
        Continuous lattices and continuous categories revisited

      • (10:40 - 11:10)
        M.-C. Pedicchio
        A characterization theorem for theories of varieties

      • (11:20 - 11:50)
        H.-E. Porst
        title to be announced

      • (12:00 - 12:30)
        J. Juerjens
        On a problem by Gabriel and Ulmer

    • (14:00 - 18:10)
      • (14:00 - 14:30)
        A. K. Simpson
        Elementary axioms for categories of classes

      • (14:40 - 15:10)
        P. Resende
        Quantale modules and observational logic

      • (15:20 - 15:50)
        R. Rother
        Strengthening of homogeneity in categorical algebra

      • (16:20 - 16:50)
        L. Polak
        On equational logic (for semigroups)

      • (17:00 - 17:30)
        M. Sekanina
        Shape in computing

      • (17:40 - 18:10)
        O. Kamenik
        title to be announced




Sunday
August 30
Satellite Workshops
  • 68th Peripathetic Seminar on Sheaves and Logic
    • (9:00 - 12:30)
      • (9:00 - 9:30)
        R. Wood
        Adjunctions for equipments

      • (9:40 - 10:10)
        E. Vitale
        On the exact completion of the homotopy category

      • (10:40 - 11:10)
        M. Jibladze
        Scattered toposes

      • (11:20 - 11:50)
        J. Velebil
        1-step cocompletions

      • (12:00 - 12:30)
        J. Rosicky
        How algebraic is algebra?






mfcs98@fi.muni.cz