CSL/MFCS'98 - Preliminary Programme

	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