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

Accepted papers

    Abdullah N. Arslan: Largest common d-dimensional subsequence of d-dimensional strings

    Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis: Analysis of approximation algorithms for k-set cover using factor-revealing linear programs

    Eric Bach, Jin-Yi Cai: A novel information transmission problem and its optimal solution

    Puneet Bhateja, Paul Gastin, Madhavan Mukund, K. Narayan Kumar: Local testing of message sequence charts is difficult

    Henrik Björklund, Thomas Schwentick: On notions of regularity for data languages

    Viviana Bono, Jaroslaw D. M. Kusmierek: FJMIP: A calculus for a modular object initialization

    Henning Bordihn, György Vaszil: Top-down deterministic parsing of languages generated by CD grammar systems

    Hans-Georg Breunig: The complexity of membership problems for circuits over sets of positive numbers

    Gaëlle Brevier, Romeo Rizzi, Stéphane Vialette: Pattern matching in protein-protein interaction graphs

    Robert Brijder, Hendrik Jan Hoogeboom, Grzegorz Rozenberg: From micro to macro: How the overlap graph determines the reduction graph in ciliates

    Robert Brijder, Miika Langille, Ion Petre: A string-based model for simple gene assembly

    Nadia Busi, Claudio Zandron: On the computational power of genetic gates with interleaving semantics: The power of inhibition and degradation

    Jin-Yi Cai, Pinyan Lu: On block-wise symmetric signatures for matchgates

    Didier Caucal, Trong Hieu Dinh: Path algorithms on regular graphs

    Miroslav Ciric, Aleksandar Stamenkovic, Jelena Ignjatovic, Tatjana Petkovic: Factorization of fuzzy automata

    Thomas Colcombet: Factorisation forests for infinite words, Application to countable scattered linear orderings

    Clelia De Felice, Gabriele Fici, Rosalba Zizza: Marked systems and circular splicing

    Sebastian Dörn, Thomas Thierauf: The quantum query complexity of algebraic properties

    Jacques Duparc, Filip Murlak: On the topological complexity of weakly recognizable tree languages

    Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara, Jan Willem Klop: Productivity of stream definitions

    Leah Epstein, Asaf Levin, Rob van Stee: Multi-dimensional packing with conflicts

    Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time

    Michael Fellows, Michael Langston, Frances Rosamond, Peter Shaw: Efficient parameterized preprocessing for cluster editing

    Gyula Győr: Representing Boolean OR functionality by quadratic polynomials modulo 6

    Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe: On the complexity of kings

    Michael Hoffmann, Richard M. Thomas: Notions of hyperbolicity in monoids

    Mihai Ionescu, Dragos Sburlan: P systems with adjoining controlled communication rules

    Michal Kunc: The simplest language where equivalence of finite substitutions is undecidable

    Martin Kutrib, Andreas Malcher: Real-time reversible iterative arrays

    Johan Kwisthout: The computational complexity of monotonicity in probabilistic networks

    Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu: Impossibility results on weakly black-box hardness amplification

    Alexander Meduna, Jirí Techet: Maximal and minimal scattered context rewriting

    Hartmut Messerschmidt, Friedrich Otto: Strictly deterministic CD-systems of restarting automata

    Rajat Mittal, Mario Szegedy: Product rules in semidefinite programming

    Alexander Okhotin: Expressive power of LL(k) Boolean grammars

    Mathias Samuelides, Luc Segoufin: Complexity of pebble tree-walking automata

    Andrea Sattler-Klein: Some complexity results for prefix Gröbner bases in free monoid rings

    Hadas Shachnai, Omer Yehezkely: Fast asymptotic FPTAS for packing fragmentable items with costs

    Takeyuki Tamura, Tatsuya Akutsu: An O(1.787n)-time algorithm for detecting a singleton attractor in a Boolean network consisting of AND/OR nodes