Theoretical Computer Science: 7th Italian Conference, ICTCS 2001 Torino, Italy, October 4–6, 2001 Proceedings

Antonio Restivo, Simona Ronchi Della Rocca, Luca Roversi (auth.)3540426728, 9783540426721

This book constitutes the refereed proceedings of the 7th Italian Conference on Theoretical Computer Science, ICTCS 2001, held in Torino, Italy in October 2001.
The 25 revised full papers presented together with two invited papers were carefully reviewed and selected from 45 submissions. The papers are organized in topical sections on lambda calculus and types, algorithms and data structures, new computing paradigms, formal languages, objects and mobility, computational complexitiy, security, and logics and logic programming.

---

Table of contents :
A LTS Semantics of Ambients via Graph Synchronization with Mobility….Pages 1-16
Filter Models and Easy Terms….Pages 17-37
Confluence of Untyped Lambda Calculus via Simple Types….Pages 38-49
Incremental Inference of Partial Types….Pages 50-73
Call-by-Value Separability and Computability….Pages 74-89
Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms….Pages 90-106
Job Shop Scheduling Problems with Controllable Processing Times….Pages 107-122
Upper Bounds on the Size of One-Way Quantum Finite Automata….Pages 123-135
P Systems with Gemmation of Mobile Membranes….Pages 136-153
Instantaneous Actions vs. Full Asynchronicity : Controlling and Coordinating a Sset of Autonomous Mobile Robots….Pages 154-171
Some Structural Properties of Associative Language Descriptions….Pages 172-183
Block-Deterministic Regular Languages….Pages 184-196
Constructing Finite Maximal Codes from Schützenberger Conjecture….Pages 197-214
An Effective Translation of Fickle into Java….Pages 215-234
Subtyping and Matching for Mobile Objects….Pages 235-255
On Synchronous and Asynchronous Communication Paradigms….Pages 256-268
Complexity of Layered Binary Search Trees with Relaxed Balance….Pages 269-284
Distance Constrained Labeling of Precolored Trees….Pages 285-292
Exponentially Decreasing Number of Operations in Balanced Trees….Pages 293-311
Directed Hypergraphs: Problems, Algorithmic Results, and a Novel Decremental Approach….Pages 312-328
Coupon Collectors, q -Binomial Coefficients and the Unsatisfiability Threshold….Pages 328-338
Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions….Pages 339-356
On the Distribution of a Key Distribution Center….Pages 357-369
Online Advertising: Secure E-coupons….Pages 370-383
A Calculus and Complexity Bound for Minimal Conditional Logic….Pages 384-404
Reasoning about Complex Actions with Incomplete Knowledge: A Modal Approach….Pages 405-426
E-unifiability via Narrowing….Pages 426-438