Erzsébet Csuhaj-Varjú / Zoltán Ésik (eds.)Fundamentals of Computation Theory
16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings
Herausgegeben:Csuhaj-Varjú, Erzsébet; Ésik, Zoltán
Invited Lectures.- Rewriting Systems with Data.- Spiking Neural P Systems: Some Characterizations.- Approximating Graphs by Graphs and Functions (Abstract).- Traces, Feedback, and the Geometry of Computation (Abstract).- Contributions.- A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings.- Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs.- A Novel Information Transmission Problem and Its Optimal Solution.- Local Testing of Message Sequence Charts Is Difficult.- On Notions of Regularity for Data Languages.- FJMIP: A Calculus for a Modular Object Initialization.- Top-Down Deterministic Parsing of Languages Generated by CD Grammar Systems.- The Complexity of Membership Problems for Circuits over Sets of Positive Numbers.- Pattern Matching in Protein-Protein Interaction Graphs.- From Micro to Macro: How the Overlap Graph Determines the Reduction Graph in Ciliates.- A String-Based Model for Simple Gene Assembly.- On the Computational Power of Genetic Gates with Interleaving Semantics: The Power of Inhibition and Degradation.- On Block-Wise Symmetric Signatures for Matchgates.- Path Algorithms on Regular Graphs.- Factorization of Fuzzy Automata.- Factorisation Forests for Infinite Words.- Marked Systems and Circular Splicing.- The Quantum Query Complexity of Algebraic Properties.- On the Topological Complexity of Weakly Recognizable Tree Languages.- Productivity of Stream Definitions.- Multi-dimensional Packing with Conflicts.- On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time.- Efficient Parameterized Preprocessing for Cluster Editing.- Representing the Boolean OR Function by Quadratic Polynomials Modulo 6.- On the Complexity of Kings.- Notions ofHyperbolicity in Monoids.- P Systems with Adjoining Controlled Communication Rules.- The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable.- Real-Time Reversible Iterative Arrays.- The Computational Complexity of Monotonicity in Probabilistic Networks.- Impossibility Results on Weakly Black-Box Hardness Amplification.- Maximal and Minimal Scattered Context Rewriting.- Strictly Deterministic CD-Systems of Restarting Automata.- Product Rules in Semidefinite Programming.- Expressive Power of LL(k) Boolean Grammars.- Complexity of Pebble Tree-Walking Automata.- Some Complexity Results for Prefix Gröbner Bases in Free Monoid Rings.- Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs.- An O(1.787 n )-Time Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes.
