SOFSEM 2011: Theory and Practice of Computer Science

Name: 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
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

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

Ivana Cerná Tibor Gyimóthy Juraj Hromkovic Keith Jeffery Rastislav Kralovic Marko Vukolic Stefan Wolf(Herausgeber*in)

Springer (Verlag)

Erschienen am 10. Januar 2011

XIV, 572 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-18381-2 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title Page
Preface
Organization
Table of Contents
Integrity and Consistency for Untrusted Services
Introduction
Contributions
Related Work
Organization
System Model
System
Functionality
Operations and Histories
Consistency Conditions
Cryptographic Primitives
Service Execution and Authentication
Separated Execution
Authenticated Separated Execution
Examples
Fork-Linearizable Execution Protocol
Conclusion
References
A Structured Codesign Approach to Many-Core Architectures for Embedded Systems
Introduction
Computing Model
Target Platform
Proof of Concept
Summary and Conclusion
References
SIMPL Systems, or: Can We Design Cryptographic Hardware without Secret Key Information?
Introduction
SIMPL Systems and Their Properties
Informal Description of SIMPL Systems
Semi-formal Specification of SIMPL Systems
Properties of SIMPL Systems
Protocols and Applications
Identification of Entities
Authentication of Messages
Application Scenarios
Implementation of SIMPL Systems
Challenges
Electrical SIMPL Systems
Integrated Optical SIMPLs
Further Implementation Strategies
Summary, Discussion, and Future Work
A First Proof-of-Concept for Optical SIMPLs
Verification of Timed-Arc Petri Nets
Introduction
Informal Introduction to Timed-Arc Petri Nets
Formal Definition of Timed-Arc Petri Nets
Syntax
Semantics
A Small Case Study: Alternating Bit Protocol
Overview of (Un)Decidability and Complexity Results
Timed Computation Tree Logic
Translations Preserving TCTL Model Checking
One-by-Many Correspondence
Translation from TAPN to Networks of Timed Automata
Conclusion
References
Efficient Algorithms for Handling Nondeterministic Automata
The Straight-Line RAC Drawing Problem Is NP-Hard
Introduction
Related Work
Preliminaries
A Class of Graphs with Unique RAC Combinatorial Embedding
The Straight-Line RAC Drawing Problem is NP-Hard
Conclusions
References
Tracking the Evolution of Code Clones
Introduction
Related Work
Approach
Clone Detection
The Evolution Mapping
Clone Smells
Evaluation
Conclusions and Future Work
References
Liquidsoap: A High-Level Programming Language for Multimedia Streaming
Liquidsoap
Streaming Model
A Language for Building Streaming Systems
Functional Transitions
Efficient Implementation
Heterogeneous Stream Contents
Clocks
Model
Clock Assignment
Related Work
Conclusion
References
Combining Traditional Map Labeling with Boundary Labeling
Motivation
Problem Definition
The (1P, Right-Sided, opo) Mixed Labeling Model
The (1P, Left-Sided, opo) Mixed Labeling Model
A Quasi-polynomial Time Solution
A 2-Approximation Algorithm
An ILP Formulation
The (1P, Two-Sided, opo) Mixed Labeling Model
Generalizations
Experimental Results
Conclusions
References
On Making a Distinguished Vertex Minimum Degree by Vertex Deletion
Introduction
Min-Degree Deletion
Fixed-Parameter Tractability Results
Non-existence of a Polynomial Kernel
Min-Indegree Deletion
Conclusion
References
Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size
Introduction
Ordered Binary Decision Diagrams
Integer Multiplication and Ordered Binary Decision Diagrams
Preliminaries
Notation
Communication Complexity
An Exponential Lower Bound on the Randomized OBDD Complexity of the Most Significant Bit of Integer Multiplication
Concluding Remarks
References
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
Introduction
Potential of a Graph
$k$-Sequences
Potential Function
Performance of GreedyMAX-type Algorithms
Family of GreedyMAX-type Algorithms
Analysis of GreedyMAX-type Algorithms
References
Sequential Optimization of Matrix Chain Multiplication Relative to Different Cost Functions
Introduction
Cost Functions
Some Cost Functions
Optimization
Sequential Optimization
An Example
Computational Complexity of Optimization
Conclusion
References
One-Reversal Counter Machines and Multihead Automata: Revisited
Introduction
Preliminaries
NCM and DPCM Are Incomparable
Counter Machines and Multihead Automata
References
Collisionless Gathering of Robots with an Extent
Introduction
Basic Model and Problem Description
The Continuous Setting
The Discrete Setting
Conclusion and Future Work
References
Min-Max Coverage in Multi-interface Networks
Introduction
Related Work
Our Results
Structure of the Paper
Preliminaries and Notation
Complexity
Approximation Results
Conclusion
References
Bandwidth Constrained Multi-interface Networks
Introduction
Definitions and Notation
Hardness and Approximation
Particular Cases, ? = 2
Conclusion
References
A Privacy-Preserving ID-Based Group Key Agreement Scheme Applied in VPAN
Introduction
ID-Based Protocol by Wan et al.
Improved Protocol
Initialisation Protocol
Join Protocol
Leave Protocol
Security and Performance Analysis
Security
Performance
Application: Virtual Private Ad Hoc Network
Conclusion and Future Work
References
White Space Regions
Introduction
Formal Problem Definition
Hardness Results
Approximation Algorithms
Non-weighted Version
Our Modification
TDCC
A Note on Measurement Units and the Root Function
Heuristic Approach
Algorithm Description
Analysis
Conclusion and Further Works
References
New Results on the Complexity of the Max- and Min-Rep Problems
Introduction
Definitions
New Results
Parameterization by $m$
Parameterization by $k$
Conclusions
References
In-Place Sorting
Introduction
Sorting with Additional Memory
Structure of the Memory
Inserting Elements in the Structure
Extracting in Sorted Order
Summary
In-Place Sorting
Concluding Remarks
References
On $d$-Regular Schematization of Embedded Paths
Introduction
Preliminaries
Hardness of 2-Regular Path Schematization
Hardness of the Union of Paths Schematization Problem
Hardness of the Path Schematization Problem
Hardness of d-Regular PSP for $d & 2$
Design and Evaluation of a MIP for $d$-Regular PSP
Conclusion
References
Upward Point-Set Embeddability
Introduction
Preliminaries
Embedding a Switch-Tree into a Point Set in Convex Position
K-Switch Trees
Upward Planar Straight-Line Point Set Embeddability is NP-Complete
Open Problems
References
Cooperative Query Answering by Abstract Interpretation
Introduction
Related Work and Motivation
Key Issues: Soundness, Relevancy, Optimality
Proposed Scheme
Transforming from Concrete to Abstract Domain
Cooperative Query Evaluation
Concretization of the Cooperative Abstract Result
Soundness, Relevancy, and Optimality
Partial Order between Cooperative Answers
Conclusions
References
An Improved B+ Tree for Flash File Systems
Introduction
How the Flash Memory Works
JFFS, JFFS2: Flash File System without Flash Index
B+ Tree
Wandering Tree
TNC: An Improved Wandering Tree
Data Structure of TNC
TNC Operations
Power Loss Handling in TNC
Experiments
Related Work
Summary
References
Comparing GPU and CPU in OLAP Cubes Creation
Introduction
GPGPU Parallel Processing Capabilities
GPGPU and Databases
OLAP Cube Creation Problem
Implementation of OLAP Cube Creation
Sequential Approach
A Naive GPGPU Solution
Improved GPGPU Solution
Parallel CPU Algorithm
Parallel GPU Devices Algorithm
Results
Experiment Set Up
CPU and GPU Performance
Conclusions
References
A Power Consumption Analysis Technique Using UML-Based Design Models in Embedded Software Development*
Introduction
Software Power Analysis
Proposed Estimation Process
Transform UML Model to CFG
Building Energy Library
EBU Detection
Power Consumption of EBU
Experiments
Experiment Environments
Accuracy of Model-Based Analysis
Elapsed Time for Analysis
Application of Model-Based Analysis Results
Conclusions and Future Work
References
Advice Complexity and Barely Random Algorithms
Introduction
Contribution and Organization of the Paper
Job Shop Scheduling
Paging
Barely Random Algorithms
Job Shop Scheduling
Paging
Advice Complexity of Job Shop Scheduling
Optimality
Competitive Ratio
References
Alternative Parameterizations for Cluster Editing
Introduction
Cluster Vertex Deletion Number
Cluster Editing
Cluster Deletion
Maximum Degree
Number of Clusters and Maximum Number of Edge Modifications per Vertex
References
The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks
Introduction
Definitions
Probabilistic Networks
The kth Most Probable Explanation Problems
Complexity Classes and Complete Problems
Complexity of Kth MPE
Complexity of K-th Partial MAP
Conclusion
References
Optimal File-Distribution in Heterogeneous and Asymmetric Storage Networks
Introduction
Preliminaries
Flow Scaling
Conclusion
References
On the Complexity of the Metric TSP under Stability Considerations
Structural Properties of Hard Metric TSP Inputs
Introduction
Related Known Results
Organization of the Paper
Preliminaries
A Win/Win Strategy for ?TSP and ?HPP_2
Implications of the Win/Win Strategy
Combined Hard Input Instances
Conclusion
References
Introduction
A Tight Upper Bound on the Stability of ?-TSP
A Polynomial Time Algorithm for 1.8-Stable Instances
The Algorithm Fails for (5/3 - $\epsilon$)-Stable Instances
Stability is Not Good for Local Search
Conclusion
References
An Automata-Theoretical Characterization of Context-Free Trace Languages
Introduction
CD-Systems of Stateless Deterministic R(1)-Automata Governed by an External Pushdown
Context-Free Trace Languages
Concluding Remarks
References
Unambiguous UML Composite Structures: The OMEGA2 Experience
Introduction
Overview of OMEGA UML
UML Composite Structures
Unambiguous Composite Structures for OMEGA UML
Typing Problems with Bidirectional Ports
Directionality Rules
Typing of Connectors
Type Coherence Rules
Port Behaviour and Further Type-Based Rules
Compiling Composite Structures to IFx
Implementation and Evaluation
Conclusions
References
Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages
Introduction
Linear Conjunctive Grammars and Trellis Automata
Visibly Pushdown Languages Are Linear Conjunctive
Languages That Are Not Linear Conjunctive
LL(k) Context-Free vs. Visibly Pushdown Languages
Conclusion
References
A Local Search Algorithm for Branchwidth
Introduction
Preliminaries
Local Search
Search Strategy
Fitness Function
Implementation
Results
Conclusions and Future Work
References
Finding the Description of Structure by Counting Method: A Case Study
Introduction
Superpositional Graphs. Definitions and Properties
Structure of the Class $SPG$
Logical Description of the Class $SPG$
Presentation of Binary Graph with Propositional Variables
Descriptive Properties of the Class $SPG$ as Propositional Formulae
Discussion
References
On Approximating the $d$-Girth of a Graph
Introduction
Hardness Results for General Graphs
Preliminaries: Some Families of Graphs
Improved Hardness Results
Approximation Algorithms for General Graphs
A Randomized $(n/log n)$-Approximation
A Better Algorithm for High-Degree Graphs
A Deterministic Algorithm for Low-Degree Graphs
Planar Graphs
Hardness Results
Approximation Algorithms
Exact Algorithms
Concluding Remarks
References
SScAC: Towards a Framework for Small-Scale Software Architectures Comparison
Introduction
Related Work
Proposal of SScAC Framework
SScAC Use Guideline
Default Goals
Case Study: Keyword in Context (KWIC)
About KWIC
Application of SScAC Framework
Evaluation
Conclusion
References
Folk Theorems on the Correspondence between State-Based and Event-Based Systems
Introduction
Preliminaries
Preservations and Reflections of Equivalences under lts and ks
Similarity
Bisimilarity
Stuttering Equivalence - Divergence-Sensitive Branching Bisimilarity
Trace Equivalence - Completed Trace Equivalence
Minimisations in LTS and KS
Minimisation in KS via Minimisation in LTS
Minimisation in LTS via Minimisation in KS
Conclusions
References
Privacy, Liveliness and Fairness for Reputation
Introduction
Related Work
The Reputation System
System Analysis
Security Analysis
Privacy Analysis
Efficiency
Conclusion
References
Minimizing Interference for the Highway Model in Wireless Ad-Hoc and Sensor Networks
Introduction
Models and Problem Definitions
Minimizing the Average Interference
No-Cross Property
Algorithms to Minimize the Average Interference
Minimizing the Maximum Interference
General Ideas
Algorithms
Analysis
Conclusion
References
Join-Queries between Two Spatial Datasets Indexed by a Single R*-Tree
Introduction
Related Work and Motivation
Background
The R*-Tree Indexing Two Spatial Datasets
Algorithms for Processing Join-Queries
The New Algorithm for 2D1T
Experimentation
Conclusions and Future Work
References
Information Leakage Analysis by Abstract Interpretation
Introduction
Concrete Domain
Sintax
Semantics
Concrete Domain
Abstract Domain
Variables Dependency Analysis
Polyhedra Analysis
Reduced Product
Analysis
Complexity
Conclusions
References
Partition into Triangles on Bounded Degree Graphs
Introduction
A Linear Time Algorithm on Graphs with $?(G) = 3$
The Relation between Partition into Triangles on Graphs with ?(G) = 4 and Exact 3-Satisfiability
Hardness Results on Graphs of Maximum Degree Four
Exponential Time Algorithms
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken