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
Published on 10. January 2011
XIV, 572 pages
978-3-642-18381-2 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Illustrations
XIV, 572 p. 140 illus., 38 illus. in color.
File size
9,09 MB
ISBN-13
978-3-642-18381-2 (9783642183812)
DOI
10.1007/978-3-642-18381-2
Schweitzer Classification
Other editions
Additional editions
Ivana Cerná | Tibor Gyimóthy | Juraj Hromkovic
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
Book
01/2011
Springer
€53.49
Shipment within 5-7 days
Content
- 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
