Theoretical Computer Science: 6th IFIP WG 2.2 International Conference, TCS 2010, Held as a Part of WCC 2010, Brisbane, Australia, September 20-23, ... in Information and Communication Technology)

IFIP Advances in Information and Communication Technology 323......Page 1
Theoretical Computer Science: 6th IFIP TC 1/WG 2.2 International Conference TCS 2010, Held as Part of WCC 2010 / Brisbane, Australia, September 20-23, 2010 / Proceedings......Page 3
IFIP World Computer Congress 2010 (WCC 2010)......Page 5
Foreword......Page 6
Conference Organization......Page 7
Table of Contents......Page 9
Introduction......Page 11
Multiset and Distribution Monads......Page 13
Convex Sets......Page 15
Prime Filters in Convex Sets......Page 17
Effect Algebras......Page 19
Effect Algebras and Convex Sets......Page 21
Effect Algebras and Convex Functors......Page 23
References......Page 28
Introduction......Page 30
The Calculus......Page 31
Bisimulation-Based Proof Method......Page 35
Properties of Mobile Ad Hoc Networks......Page 37
References......Page 41
Introduction......Page 42
Labelled Transition Systems and a Selection of Composition Operators......Page 45
Safety Properties......Page 48
Liveness Properties......Page 51
Conditional Liveness Properties......Page 55
Linear Time Properties......Page 59
References......Page 61
Entropy and Attack Models in Information Flow......Page 63
References......Page 64
Introduction......Page 65
Probabilistic Automata......Page 67
Systems......Page 68
Components......Page 69
Systems......Page 70
Admissible Schedulers......Page 71
Restricting Local Schedulers......Page 72
Safe Bisimilarity......Page 73
Safe Nondeterministic Information Hiding......Page 75
Related Work......Page 77
Conclusion and Future Work......Page 78
References......Page 79
Introduction......Page 81
Preliminaries......Page 82
Probabilistic Game Structures......Page 83
Probabilistic Alternating-Time Temporal Logic......Page 85
Probabilistic Alternating Simulation Relations......Page 89
Forward I-Simulation Is Sound for I-PATL......Page 90
Probabilistic Alternating Bisimulation......Page 93
Conclusion and Future Work......Page 94
References......Page 95
Introduction......Page 96
The Calculus......Page 98
Label Transition System......Page 100
Weak Bisimulation......Page 102
Characterization......Page 105
The Zeroconf Protocol......Page 107
Conclusion and Future Works......Page 109
References......Page 110
Introduction......Page 111
Preliminaries......Page 113
A Generalization of the Result of Chung et al.......Page 114
The NP-Hardness Proof of k-SBP Revisited......Page 118
Conclusion......Page 119
References......Page 120
The Framework......Page 121
Problems and Contributions......Page 122
Definitions and Terminology......Page 124
Problems and Basic Limitations......Page 126
TDBroadcast[foremost] in R......Page 127
TDBroadcast[foremost] in B......Page 129
TDBroadcast[shortest] in B......Page 131
References......Page 133
Introduction......Page 135
Behavior Trees......Page 136
Slicing of Behavior Trees......Page 139
Creating the BT Dependence Graph......Page 140
Creating the Slice......Page 143
Case Study: The e-Health System......Page 144
Slicing the Model of the e-Health System......Page 146
References......Page 148
Introduction......Page 150
Proposed Algorithm......Page 151
Linear Bounding Containers......Page 153
Anisotropic Gaussian Kernel......Page 154
Reference Text Line......Page 155
Text Segmentation Experiment and Results......Page 156
Skew Rate Text Experiment and Results......Page 158
References......Page 162
Introduction......Page 163
Linear XML Patterns with Gaps and Wildcards......Page 165
The Matching Algorithm......Page 166
Correctness and Complexity......Page 167
Fast Backtracking......Page 170
Experimental Analysis......Page 172
Conclusion......Page 173
References......Page 174
Introduction......Page 175
Abstract Machines and Sequent Calculus......Page 176
A Language for LK Proofs......Page 178
A Syntax for Focalised Classical Logic......Page 181
Encodings......Page 184
A Synthetic System......Page 186
Conclusion......Page 189
References......Page 190
Introduction......Page 192
Polarized Deduction Modulo......Page 194
Clausal Rewrite Systems......Page 196
Polarized Resolution Modulo......Page 198
Soundness and Completeness......Page 199
References......Page 206
Introduction......Page 207
Preliminaries......Page 208
A Logic on Subobjects......Page 210
Monadic Second-Order Graph Logic......Page 212
From the Logic on Subobjects to Monadic Second-Order Logic......Page 213
Logic and Recognizability......Page 214
Detailed Example......Page 219
Conclusion and Further Research......Page 220
References......Page 222
Introduction......Page 223
Preliminaries......Page 224
Branches......Page 225
Evidence and Pre-evidence......Page 226
Tableau Rules......Page 227
Blocking Conditions and Quasi-evidence......Page 229
Termination......Page 232
Conclusion......Page 236
References......Page 237
Introduction......Page 239
Applied Pi Calculus......Page 241
Symbolic Semantics......Page 242
Proof System......Page 246
Finiteness of Partition......Page 251
Conclusions......Page 252
References......Page 253
Introduction......Page 254
Concurrent Pattern Calculus......Page 255
Syntax......Page 256
Operational Semantics......Page 257
Trade......Page 258
Some Process Calculi......Page 261
Valid Encodings and Their Properties......Page 262
CPC vs. -Calculus and Linda......Page 264
CPC vs. Spi......Page 265
References......Page 267
Introduction......Page 269
Characterising Strong Randomness......Page 271
Characterising Demuth Randomness......Page 276
Characterising Turing-Incomplete Martin-Löf Random Sets......Page 277
Conclusion and Future Work......Page 279
References......Page 280
Topologies Refining the Cantor Topology on X$^ω$......Page 281
Topological Spaces in General......Page 282
The Cantor-Space: Basic Properties......Page 283
Topologies Refining the Cantor Topology......Page 284
The Automatic Topology......Page 287
The Alphabetic Topologies......Page 289
The Büchi Topology and the Hierarchy of Topologies......Page 290
Metrisability......Page 291
General Properties......Page 292
U–Topology......Page 293
References......Page 294
Introduction......Page 296
Ordered Binary Decision Diagrams......Page 298
The Maximum Matching Problem on OBDD-Represented Graphs......Page 300
Exponential Blow-Ups for the OBDD-Complexity of Directed and Undirected Graphs......Page 305
References......Page 309
Introduction and Overview......Page 311
Traceability......Page 312
Autocomplex and Complex Sets......Page 316
Diagonally Noncomputable Sets......Page 317
Equivalences of the Almost Everwhere Notions......Page 318
Equivalence of the Infinitely Often Notions......Page 320
Computable Traces and Total Machines......Page 321
Characterizing i.o. Complex and i.o. Autocomplex via Lower Bounds on the Complexity of Initial Segments......Page 322
Time Bounded Traceability and Complexity......Page 323
References......Page 325
Problem Statement......Page 326
Principle and Definitions......Page 328
Phase 1......Page 329
Phase 3......Page 330
Main Algorithm......Page 332
From the Preallocation to the Final Schedule......Page 334
Complexity......Page 335
Toward Better Approximation Ratios......Page 336
References......Page 337
Introduction......Page 338
The Unit Price Problem......Page 341
An Upper Bound......Page 342
An Upper Bound for Worst-Fit......Page 343
An Upper Bound......Page 344
Lower Bounds for First-Fit and Best-Fit......Page 346
References......Page 348
Introduction......Page 350
Semirings and Formal Power Series......Page 352
A Process Calculus......Page 354
Abstract Semantics......Page 356
A Compositional Construction......Page 357
Modeling a ``Single Bid'' Auction......Page 358
Imperative Computations......Page 360
Parallelism......Page 362
References......Page 363
Introduction......Page 365
Modeling Routing in Dynamic Networks via Games......Page 367
Toy Example......Page 371
Negative Results......Page 372
Solving Games with the Delivery Winning Condition......Page 373
Solving Games under Weak Constraints......Page 374
Conclusion and Perspective......Page 378
References......Page 379
Introduction......Page 381
Specification Semantics......Page 383
Implementation Semantics......Page 384
Constraints on the Memory Model......Page 385
Locks......Page 387
Sequential Consistency......Page 388
Barriers......Page 389
Sequential Consistency......Page 390
Modeling Multiprocessors with Caches......Page 391
Modeling Update-Based Protocols......Page 392
Relaxing the Unlocking condition......Page 393
Related and Future Work......Page 394
References......Page 395
Author Index......Page 396