Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings

Ahmed Bouajjani, Peter Habermehl, Yan Jurski, Mihaela Sighireanu (auth.), Erzsébet Csuhaj-Varjú, Zoltán Ésik (eds.)9783540742395, 3540742395

The 16th International Symposium on Fundamentals of Computation Theory was held in Budapest, Hungary, in August 2007. This symposium drew leading minds in computation theory from around the world to present their findings and discuss new developments in the field. This volume constitutes the refereed proceedings of the symposium.

Thirty-nine full papers are presented along with four invited papers. All the papers were carefully reviewed by the editors to ensure that each one meets the highest standards of research and scholarship.

The papers address current topics in computation theory, including automata and formal languages, design and analysis of algorithms, computational and structural complexity, semantics, logic, algebra and categories in computer science, circuits and networks, learning theory, specification and verification, parallel and distributed systems, concurrency theory, cryptography and cryptographic protocols, approximation and randomized algorithms, computational geometry, quantum computation and information, and bio-inspired computation.

---

Table of contents :
Front Matter….Pages –
Rewriting Systems with Data….Pages 1-22
Spiking Neural P Systems: Some Characterizations….Pages 23-37
Approximating Graphs by Graphs and Functions (Abstract)….Pages 38-38
Traces, Feedback, and the Geometry of Computation (Abstract)….Pages 39-39
A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings….Pages 40-51
Analysis of Approximation Algorithms for k -Set Cover Using Factor-Revealing Linear Programs….Pages 52-63
A Novel Information Transmission Problem and Its Optimal Solution….Pages 64-75
Local Testing of Message Sequence Charts Is Difficult….Pages 76-87
On Notions of Regularity for Data Languages….Pages 88-99
FJMIP: A Calculus for a Modular Object Initialization….Pages 100-112
Top-Down Deterministic Parsing of Languages Generated by CD Grammar Systems….Pages 113-124
The Complexity of Membership Problems for Circuits over Sets of Positive Numbers….Pages 125-136
Pattern Matching in Protein-Protein Interaction Graphs….Pages 137-148
From Micro to Macro: How the Overlap Graph Determines the Reduction Graph in Ciliates….Pages 149-160
A String-Based Model for Simple Gene Assembly….Pages 161-172
On the Computational Power of Genetic Gates with Interleaving Semantics: The Power of Inhibition and Degradation….Pages 173-186
On Block-Wise Symmetric Signatures for Matchgates….Pages 187-198
Path Algorithms on Regular Graphs….Pages 199-212
Factorization of Fuzzy Automata….Pages 213-225
Factorisation Forests for Infinite Words….Pages 226-237
Marked Systems and Circular Splicing….Pages 238-249
The Quantum Query Complexity of Algebraic Properties….Pages 250-260
On the Topological Complexity of Weakly Recognizable Tree Languages….Pages 261-273
Productivity of Stream Definitions….Pages 274-287
Multi-dimensional Packing with Conflicts….Pages 288-299
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time….Pages 300-311
Efficient Parameterized Preprocessing for Cluster Editing….Pages 312-321
Representing the Boolean OR Function by Quadratic Polynomials Modulo 6….Pages 322-327
On the Complexity of Kings….Pages 328-340
Notions of Hyperbolicity in Monoids….Pages 341-352
P Systems with Adjoining Controlled Communication Rules….Pages 353-364
The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable….Pages 365-375
Real-Time Reversible Iterative Arrays….Pages 376-387
The Computational Complexity of Monotonicity in Probabilistic Networks….Pages 388-399
Impossibility Results on Weakly Black-Box Hardness Amplification….Pages 400-411
Maximal and Minimal Scattered Context Rewriting….Pages 412-423
Strictly Deterministic CD-Systems of Restarting Automata….Pages 424-434
Product Rules in Semidefinite Programming….Pages 435-445
Expressive Power of LL( k ) Boolean Grammars….Pages 446-457
Complexity of Pebble Tree-Walking Automata….Pages 458-469
Some Complexity Results for Prefix Gröbner Bases in Free Monoid Rings….Pages 470-481
Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs….Pages 482-493
An O (1.787 n )-Time Algorithm for Detecting a Singleton Attractor in a Boolean Network Consisting of AND/OR Nodes….Pages 494-505
Back Matter….Pages –