Ebook: SOFSEM 2011: Theory and Practice of Computer Science: 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011. Proceedings

This book constitutes the refereed proceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011, held in Nový, Smokovec, Slovakia in January 2011. The 41 revised full papers, presented together with 5 invited contributions, were carefully reviewed and selected from 122 submissions. SOFSEM 2011 was organized around the following four tracks: foundations of computer science; software, systems, and services; processing large datasets; and cryptography, security, and trust.

---

This book constitutes the refereed proceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011, held in Nov?, Smokovec, Slovakia in January 2011. The 41 revised full papers, presented together with 5 invited contributions, were carefully reviewed and selected from 122 submissions. SOFSEM 2011 was organized around the following four tracks: foundations of computer science; software, systems, and services; processing large datasets; and cryptography, security, and trust.

---

This book constitutes the refereed proceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011, held in Nov?, Smokovec, Slovakia in January 2011. The 41 revised full papers, presented together with 5 invited contributions, were carefully reviewed and selected from 122 submissions. SOFSEM 2011 was organized around the following four tracks: foundations of computer science; software, systems, and services; processing large datasets; and cryptography, security, and trust.
Content:
Front Matter....Pages -
Integrity and Consistency for Untrusted Services....Pages 1-14
A Structured Codesign Approach to Many-Core Architectures for Embedded Systems....Pages 15-25
SIMPL Systems, or: Can We Design Cryptographic Hardware without Secret Key Information?....Pages 26-45
Verification of Timed-Arc Petri Nets....Pages 46-72
Efficient Algorithms for Handling Nondeterministic Automata....Pages 73-73
The Straight-Line RAC Drawing Problem Is NP-Hard....Pages 74-85
Tracking the Evolution of Code Clones....Pages 86-98
Liquidsoap: A High-Level Programming Language for Multimedia Streaming....Pages 99-110
Combining Traditional Map Labeling with Boundary Labeling....Pages 111-122
On Making a Distinguished Vertex Minimum Degree by Vertex Deletion....Pages 123-134
Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size....Pages 135-145
GreedyMAX-type Algorithms for the Maximum Independent Set Problem....Pages 146-156
Sequential Optimization of Matrix Chain Multiplication Relative to Different Cost Functions....Pages 157-165
One-Reversal Counter Machines and Multihead Automata: Revisited....Pages 166-177
Collisionless Gathering of Robots with an Extent....Pages 178-189
Min-Max Coverage in Multi-interface Networks....Pages 190-201
Bandwidth Constrained Multi-interface Networks....Pages 202-213
A Privacy-Preserving ID-Based Group Key Agreement Scheme Applied in VPAN....Pages 214-225
White Space Regions....Pages 226-237
New Results on the Complexity of the Max- and Min-Rep Problems....Pages 238-247
In-Place Sorting....Pages 248-259
On d-Regular Schematization of Embedded Paths....Pages 260-271
Upward Point-Set Embeddability....Pages 272-283
Cooperative Query Answering by Abstract Interpretation....Pages 284-296
An Improved B+ Tree for Flash File Systems....Pages 297-307
Comparing GPU and CPU in OLAP Cubes Creation....Pages 308-319
A Power Consumption Analysis Technique Using UML-Based Design Models in Embedded Software Development....Pages 320-331
Advice Complexity and Barely Random Algorithms....Pages 332-343
Alternative Parameterizations for Cluster Editing....Pages 344-355
The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks....Pages 356-367
Optimal File-Distribution in Heterogeneous and Asymmetric Storage Networks....Pages 368-381
On the Complexity of the Metric TSP under Stability Considerations....Pages 382-393
Structural Properties of Hard Metric TSP Inputs....Pages 394-405
An Automata-Theoretical Characterization of Context-Free Trace Languages....Pages 406-417
Unambiguous UML Composite Structures: The OMEGA2 Experience....Pages 418-430
Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages....Pages 431-443
A Local Search Algorithm for Branchwidth....Pages 444-454
Finding the Description of Structure by Counting Method: A Case Study....Pages 455-466
On Approximating the d-Girth of a Graph....Pages 467-481
SScAC: Towards a Framework for Small-Scale Software Architectures Comparison....Pages 482-493
Folk Theorems on the Correspondence between State-Based and Event-Based Systems....Pages 494-505
Privacy, Liveliness and Fairness for Reputation....Pages 506-519
Minimizing Interference for the Highway Model in Wireless Ad-Hoc and Sensor Networks....Pages 520-532
Join-Queries between Two Spatial Datasets Indexed by a Single R*-Tree....Pages 533-544
Information Leakage Analysis by Abstract Interpretation....Pages 545-557
Partition into Triangles on Bounded Degree Graphs....Pages 558-569
Back Matter....Pages -

---

This book constitutes the refereed proceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011, held in Nov?, Smokovec, Slovakia in January 2011. The 41 revised full papers, presented together with 5 invited contributions, were carefully reviewed and selected from 122 submissions. SOFSEM 2011 was organized around the following four tracks: foundations of computer science; software, systems, and services; processing large datasets; and cryptography, security, and trust.
Content:
Front Matter....Pages -
Integrity and Consistency for Untrusted Services....Pages 1-14
A Structured Codesign Approach to Many-Core Architectures for Embedded Systems....Pages 15-25
SIMPL Systems, or: Can We Design Cryptographic Hardware without Secret Key Information?....Pages 26-45
Verification of Timed-Arc Petri Nets....Pages 46-72
Efficient Algorithms for Handling Nondeterministic Automata....Pages 73-73
The Straight-Line RAC Drawing Problem Is NP-Hard....Pages 74-85
Tracking the Evolution of Code Clones....Pages 86-98
Liquidsoap: A High-Level Programming Language for Multimedia Streaming....Pages 99-110
Combining Traditional Map Labeling with Boundary Labeling....Pages 111-122
On Making a Distinguished Vertex Minimum Degree by Vertex Deletion....Pages 123-134
Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size....Pages 135-145
GreedyMAX-type Algorithms for the Maximum Independent Set Problem....Pages 146-156
Sequential Optimization of Matrix Chain Multiplication Relative to Different Cost Functions....Pages 157-165
One-Reversal Counter Machines and Multihead Automata: Revisited....Pages 166-177
Collisionless Gathering of Robots with an Extent....Pages 178-189
Min-Max Coverage in Multi-interface Networks....Pages 190-201
Bandwidth Constrained Multi-interface Networks....Pages 202-213
A Privacy-Preserving ID-Based Group Key Agreement Scheme Applied in VPAN....Pages 214-225
White Space Regions....Pages 226-237
New Results on the Complexity of the Max- and Min-Rep Problems....Pages 238-247
In-Place Sorting....Pages 248-259
On d-Regular Schematization of Embedded Paths....Pages 260-271
Upward Point-Set Embeddability....Pages 272-283
Cooperative Query Answering by Abstract Interpretation....Pages 284-296
An Improved B+ Tree for Flash File Systems....Pages 297-307
Comparing GPU and CPU in OLAP Cubes Creation....Pages 308-319
A Power Consumption Analysis Technique Using UML-Based Design Models in Embedded Software Development....Pages 320-331
Advice Complexity and Barely Random Algorithms....Pages 332-343
Alternative Parameterizations for Cluster Editing....Pages 344-355
The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks....Pages 356-367
Optimal File-Distribution in Heterogeneous and Asymmetric Storage Networks....Pages 368-381
On the Complexity of the Metric TSP under Stability Considerations....Pages 382-393
Structural Properties of Hard Metric TSP Inputs....Pages 394-405
An Automata-Theoretical Characterization of Context-Free Trace Languages....Pages 406-417
Unambiguous UML Composite Structures: The OMEGA2 Experience....Pages 418-430
Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages....Pages 431-443
A Local Search Algorithm for Branchwidth....Pages 444-454
Finding the Description of Structure by Counting Method: A Case Study....Pages 455-466
On Approximating the d-Girth of a Graph....Pages 467-481
SScAC: Towards a Framework for Small-Scale Software Architectures Comparison....Pages 482-493
Folk Theorems on the Correspondence between State-Based and Event-Based Systems....Pages 494-505
Privacy, Liveliness and Fairness for Reputation....Pages 506-519
Minimizing Interference for the Highway Model in Wireless Ad-Hoc and Sensor Networks....Pages 520-532
Join-Queries between Two Spatial Datasets Indexed by a Single R*-Tree....Pages 533-544
Information Leakage Analysis by Abstract Interpretation....Pages 545-557
Partition into Triangles on Bounded Degree Graphs....Pages 558-569
Back Matter....Pages -
....