Theoretical Computer Science: 8th Italian Conference, ICTCS 2003, Bertinoro, Italy, October 13-15, 2003. Proceedings

Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Paul Spirakis (auth.), Carlo Blundo, Cosimo Laneve (eds.)3540202161, 9783540202165

This book constitutes the refereed proceedings of the 8th Italian Conference on Theoretical Computer Science, ICTCS 2003, held in Bertinoro, Italy in October 2003.

The 27 revised full papers presented together with an invited paper and abstracts of 2 invited talks were carefully reviewed and selected from 65 submissions. The papers are organized in topical sections on program design-models and analysis, algorithms and complexity, semantics and formal languages, and security and cryptography.

---

Table of contents :
Front Matter….Pages –
Extreme Nash Equilibria….Pages 1-20
Certification of Memory Usage….Pages 21-21
On Programming Models for Mobility….Pages 22-22
On the Computational Complexity of Cut-Elimination in Linear Logic….Pages 23-36
A Constructive Proof of the Soundness of the Encoding of Random Access Machines in a Linda Calculus with Ordered Semantics….Pages 37-57
Finite Horizon Analysis of Stochastic Systems with the Mur φ Verifier….Pages 58-71
Towards Compact and Tractable Automaton-Based Representations of Time Granularities….Pages 72-85
Lower Bounds on the Size of Quantum Automata Accepting Unary Languages….Pages 86-96
Refined Effects for Unanticipated Object Re-classification: $mathcal{F}ickle_{rm 3}$ ….Pages 97-110
Cost Constrained Fixed Job Scheduling….Pages 111-124
A Work-Optimal Coarse-Grained PRAM Algorithm for Lexicographically First Maximal Independent Set….Pages 125-136
An Approximation Algorithm for the Minimum Weight Vertex-Connectivity Problem in Complete Graphs with Sharpened Triangle Inequality….Pages 137-149
Channel Assignment in Honeycomb Networks….Pages 150-162
Exact Solution of a Class of Frequency Assignment Problems in Cellular Networks….Pages 163-173
The Complexity of Checking Consistency of Pedigree Information and Related Problems….Pages 174-187
On Clausal Equivalence and Hull Inclusion….Pages 188-201
Logical Semantics for the First Order ς -Calculus….Pages 202-215
On the Expressive Power of Light Affine Logic….Pages 216-227
Reasoning about Self and Others: Communicating Agents in a Modal Action Logic….Pages 228-241
Decidability Properties of Recursive Types….Pages 242-255
Algebraic Theories for Contextual Pre-nets….Pages 256-270
A Coalgebraic Description of Web Interactions….Pages 271-283
A Calculus for Dynamic Linking….Pages 284-301
Towards a Smart Compilation Manager for Java….Pages 302-315
Anonymous Group Communication in Mobile Networks….Pages 316-328
Aspects of Pseudorandomness in Nonlinear Generators of Binary Sequences….Pages 329-341
An Information-Theoretic Approach to the Access Control Problem….Pages 342-354
Security-Aware Program Transformations….Pages 355-368
Information Flow Security and Recursive Systems….Pages 369-382
Compositional Verification of Secure Streamed Data: A Case Study with EMSS….Pages 383-396
Back Matter….Pages –