Theoretical Computer Science

Guiseppe F. Italiano, Eugenio Moggi, Luigi Laura9789812770981, 981-277-098-4

Many researchers from different countries converged at the 10th Italian Conference on Theoretical Computer Science (ICTCS 2007) to discuss recent developments in theoretical computer science. The volume contains all contributed papers selected for presentation with the invited lectures delivered. The subjects of this book range from logical and mathematical aspects of computing, design and analysis of algorithms, to semantics of programming languages.

---

Table of contents :
CONTENTS……Page 12
Preface……Page 6
A Short Research Biography of Mario Coppo, Mariangiola Dezani-Ciancaglini, and Simona Ronchi Della Rocca……Page 8
ICTCS 2007: October 3-5 2007, Rome, Italy……Page 10
Part A Invited Talks……Page 16
Clairvoyance and Laziness for on Line Travelling Agents G. Ausiello……Page 18
Proving the Range Property for Lambda Theories and Models H. Barendregt……Page 19
Bibliography……Page 20
1. Introduction……Page 21
Bibliography……Page 24
Bibliography……Page 26
Part B Regular Contributions……Page 28
1. Introduction……Page 30
3. The -Dense Steiner Tree Problem……Page 33
3.1. Towards Average-Density: Relaxing the Density Condition……Page 35
4. The Dense Steiner Forest Problem……Page 38
References……Page 40
Weak Pattern Matching in Colored Graphs: Minimizing the Number of Connected Components R. Dondi, G. Fertin, and S. Vialette……Page 42
1. Introduction……Page 43
3. Hardness result for paths……Page 44
4. Fixed-parameter algorithms……Page 45
4.1. The MIN-CC problem is fixed-parameter tractable……Page 46
4.2. A faster fixed-parameter algorithm for trees……Page 47
5. A polynomial-time algorithm for paths with a bounded number of colors……Page 49
6. Hardness of approximation for trees……Page 50
8. Conclusion……Page 52
Bibliography……Page 53
1. Introduction……Page 54
2. Extended Markovian Process Algebra……Page 56
3.1. Extended Markovian Bisimilarity……Page 60
3.2. Abstracting from Internal Immediate Actions……Page 62
3.3. Congruence Result for Well-Prioritized Terms……Page 66
3.4. Axioms for Non-Recursive Well-Prioritized Terms……Page 68
4. Conclusion……Page 70
References……Page 71
1. Introduction……Page 72
2. Preliminaries……Page 75
3. Class-Oriented Abstract Non-Interference……Page 77
4. ANI Analysis for Class Information……Page 78
5. An Example……Page 81
6. Conclusions and FutureWork……Page 82
References……Page 83
1. Introduction……Page 85
3. The Algorithm……Page 87
4. Analysis……Page 92
References……Page 95
Seeing the Trees and their Branches in the Network is Hard I. A. Kanj, L. Nakhleh, C. Than, and G. Xia……Page 97
1. Introduction……Page 98
2. Phylogenetic Networks, Trees, and the Infinite Site Model……Page 99
4.2. A Parameterized Algorithm for ISPN……Page 102
Bibliography……Page 107
1. Introduction……Page 109
2. Fuzzy Sets……Page 111
3. Fuzzy Labelled Transition Systems……Page 113
4. Fuzzy Hennessy-Milner Logic……Page 115
4.1. FHML with recursion……Page 117
5. Conclusions and FutureWorks……Page 118
Bibliography……Page 119
1. Introduction……Page 121
2. An abstract framework……Page 123
3. Linking by entailment……Page 125
4. Compositional compilation and principal typings……Page 127
5. Linking by environment entailment and subtyping……Page 128
6. Conclusion……Page 130
Bibliography……Page 131
1. Introduction……Page 133
2. A type system with polymorphic method types……Page 134
3. Inferring polymorphic method types……Page 139
4. Related and further work……Page 141
Bibliography……Page 143
1. Introduction……Page 145
2. Algorithm……Page 147
3. Lower Bound……Page 151
4. FutureWork……Page 152
Bibliography……Page 153
1. Introduction……Page 154
2. Derangements……Page 156
3. The Triangle of First Fixed Points……Page 159
4. Mean and Variance……Page 163
Bibliography……Page 165
1. Introduction……Page 166
3. Separating PTAS from EPTAS……Page 168
4. Oracle Constructions……Page 171
Bibliography……Page 176
1. Introduction……Page 178
2. The Dynamical Systems Framework……Page 180
3.1. Transition Classes……Page 181
3.2. Network Classes……Page 183
4. Islands of Tractability for Fixed Point Counting……Page 184
4.1. The Case of Local Transition Functions Given By Lookup Tables……Page 185
Bibliography……Page 187
Introduction……Page 190
1.1. Variants of Presburger arithmetic……Page 191
2.2. Linear sets……Page 192
3.1. Closure properties……Page 194
3.2. Quasisimple sets……Page 196
4.1. An algebraic characterization of definable sets……Page 197
4.2. A special case……Page 198
4.3. The procedure……Page 200
Bibliography……Page 201
1. Introduction……Page 202
2. Defining Proofs of Knowledge in the BPK Model……Page 205
3. Separating the Notions ofWitness Extraction……Page 210
4. ConcurrentWitness Extraction……Page 211
Bibliography……Page 212
Author Index……Page 214