Theoretical Computer Science: 9th Italian Conference, ICTCS 2005, Siena, Italy, October 12-14, 2005. Proceedings

Giuseppe Castagna (auth.), Mario Coppo, Elena Lodi, G. Michele Pinna (eds.)3540291067, 9783540291060

This book constitutes the refereed proceedings of the 9th International Conference on Theoretical Computer Science, ICTCS 2005, held at the Certosa di Pontignano, Siena, Italy, in October 2005.

The 29 revised full papers presented together with an invited paper and abstracts of 2 invited talks were carefully reviewed and selected from 83 submissions. The papers address all current issues in theoretical computer science and focus especially on analysis and design of algorithms, computability, computational complexity, cryptography, formal languages and automata, foundations of programming languages and program analysis, natural computing paradigms (quantum computing, bioinformatics), program specification and verification, term rewriting, theory of logical design and layout, type theory, security, and symbolic and algebraic computation.

---

Table of contents :
Front Matter….Pages –
Semantic Subtyping: Challenges, Perspectives, and Open Problems….Pages 1-20
Biological Systems as Reactive Systems….Pages 21-21
Mobile Agents Computing: Security Issues and Algorithmic Solutions….Pages 22-22
Efficient Algorithms for Detecting Regular Point Configurations….Pages 23-35
Pickup and Delivery for Moving Objects on Broken Lines….Pages 36-50
A Static Analysis of PKI-Based Systems….Pages 51-65
Subtyping Object and Recursive Types Logically….Pages 66-80
The Language χ : Circuits, Computations and Classical Logic….Pages 81-96
Checking Risky Events Is Enough for Local Policies….Pages 97-112
The Graph Rewriting Calculus: Confluence and Expressiveness….Pages 113-127
Safe Object Composition in the Presence of Subtyping….Pages 128-142
Reachability Analysis in Boxed Ambients….Pages 143-159
Error Mining for Regular Expression Patterns….Pages 160-172
Reconstructing an Alternate Periodical Binary Matrix from Its Orthogonal Projections….Pages 173-181
Inapproximability Results for the Lateral Gene Transfer Problem….Pages 182-195
Faster Deterministic Wakeup in Multiple Access Channels….Pages 196-204
Weighted Coloring: Further Complexity and Approximability Results….Pages 205-214
Quantum Algorithms for a Set of Group Theoretic Problems….Pages 215-227
On the Computational Complexity of the L (2,1) -Labeling Problem for Regular Graphs….Pages 228-236
A Polymerase Based Algorithm for SAT….Pages 237-250
Laxity Helps in Broadcast Scheduling….Pages 251-264
Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory….Pages 265-279
Synthesis from Temporal Specifications Using Preferred Answer Set Programming….Pages 280-294
Model Checking Strategic Abilities of Agents Under Incomplete Information….Pages 295-308
Improved Algorithms for Polynomial-Time Decay and Time-Decay with Additive Error….Pages 309-322
A Theoretical Analysis of Alignment and Edit Problems for Trees….Pages 323-337
A Complete Formulation of Generalized Affine Equivalence….Pages 338-347
A New Combinatorial Approach to Sequence Comparison….Pages 348-359
A Typed Assembly Language for Non-interference….Pages 360-374
Improved Exact Exponential Algorithms for Vertex Bipartization and Other Problems….Pages 375-389
A Typed Semantics of Higher-Order Store and Subtyping….Pages 390-405
Two Variables Are Not Enough….Pages 406-409
Back Matter….Pages –