SOFSEM 2012: Theory and Practice of Computer Science
38th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 21-27, 2012, Proceedings
Published on 18. January 2012
XVII, 674 pages
978-3-642-27660-6 (ISBN)
Description
This book constitutes the refereed proceedings of the 38th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2012, held in Spindleruv Mlýn, Czech Republic, in January 2012.
The 43 revised papers presented in this volume were carefully reviewed and selected from 121 submissions. The book also contains 11 invited talks, 10 of which are in full-paper length. The contributions are organized in topical sections named: foundations of computer science; software and Web engineering; cryptography, security, and verification; and artificial intelligence.
More details
Other editions
Additional editions
Maria Bielikova | Gerhard Friedrich | Georg Gottlob
SOFSEM 2012: Theory and Practice of Computer Science
38th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 21-27, 2012, Proceedings
Book
01/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Talks
- Foundations of Computer Science
- The Legacy of Turing in Numerical Analysis
- Introduction
- Complexity and Accuracy
- Accuracy
- Complexity
- References
- Turing Machines for Dummies Why Representations Do Matter
- The Turing Machine Model
- The Chomsky Hierarchy and the Corresponding Automata
- Master Reductions for NP
- Stockmeyer and His Work on Regular Expressions
- The Impact of the Intrinsic Representation on Machine Models in the Second Machine Class
- Conclusion - Is There a Dragon Out There?
- References
- What Is an Algorithm?
- Introduction
- Can the Notion of Algorithm Be Rigorously Defined?
- Remarks on Turing's Analysis of Computation
- Gandy's Analysis of Mechanisms
- What Kind of Entities Are Algorithms?
- Moschovakis's Recursion-Based Approach
- References
- Strong Bridges and Strong Articulation Points of Directed Graphs
- Towards Computational Models of Artificial Cognitive Systems That Can, in Principle, Pass the Turing Test
- Introduction
- Status Quo
- Watson the Computer
- Winds of Change
- A Non-biological Model of a Conscious Cognitive System
- HUGO
- Towards Higher Level Cognitive Functions
- Conclusions
- References
- Software and Web Engineering
- A Fully Generic Approach for Realizing the Adaptive Web
- Introduction
- A Brief Overview of Adaptive Applications and Platforms
- The GALE Architecture
- GALE Processors and Modules
- The Execution of GALE Adaptation Rules
- GAM: The GALE Adaptation Model (GALE Code)
- Conclusions and Further Work
- References
- Multi Feature Indexing Network MUFIN for Similarity Search Applications
- Motivation
- Challenges
- Digital Data Explosion
- Similarity Management of Data
- The Main Research Objectives
- The MUFIN Approach
- The Vision
- The Underlying Paradigms
- Demonstrations and Applications
- Future Trends and Conclusions
- References
- Cryptography, Security, and Verification
- Recent Challenges and Ideas in Temporal Synthesis
- Introduction
- Preliminaries
- Algorithms
- Methodology
- Scope
- Quality
- References
- Cryptography from Learning Parity with Noise
- Learning Parity with Noise and Related Problems
- Efficient LPN Based Cryptosystems
- Conclusions and Open Problems
- References
- Artificial Intelligence
- A Quick Tour of Word Sense Disambiguation, Induction and Related Approaches
- Introduction
- Word Sense Disambiguation
- Sense Representation
- Techniques
- Performance
- Knowledge
- Multilinguality
- Domain WSD
- Word Sense Induction
- Techniques
- Evaluation
- Coverage
- Lexical Substitution
- Other Techniques
- Compositionality and Meaning
- Conclusions
- References
- Not Another Look at the Turing Test!
- Introduction
- What Does the Turing Test Test?
- Loebner Competition
- Can a Machine Tell a Joke?
- Turing 2008
- Argument from Disability
- It Doesn't Take Much to Fool a Philosopher
- Conclusions
- Answer to Puzzle
- References
- Regular Papers
- Foundations of Computer Science
- The Equational Theory of Weak Complete Simulation Semantics over BCCSP
- Introduction
- Preliminaries
- Weak Complete Simulation
- Ground-Complete Axiomatizations
- Nonexistence of Finite Complete Axiomatizations
- Conclusion
- References
- Complexity Insights of the Minimum Duplication Problem
- Introduction
- On a Tight Inapproximability
- A Randomized Approach
- Conclusion
- References
- A Turing Machine Resisting Isolated Bursts of Faults
- Introduction
- The Structure of the State, Cells, and Simulation
- Computation Phase
- Spreading Phase
- Coping with Faults
- The Recovery Procedure
- A Road-Map for the Proof of the Main Theorem
- References
- Properties of SLUR Formulae
- Introduction
- Definitions and Results
- Every Canonical CNF Is a SLUR CNF
- Testing Whether a Given CNF Is SLUR Is coNP Complete
- Hierarchy SLUR(i)
- References
- Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs
- Introduction
- Preliminaries
- General Hypergraphs
- Tree Graphs
- Upper Bound for Unique-Maximum Number of Binary Trees
- Upper Bound for Unique-Maximum Number of Arbitrary Trees
- Trees with Different Unique-Maximum and Conflict-Free Numbers
- Discussion and Open Problems
- References
- Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration
- Introduction
- Preliminaries
- Preliminaries on Branching
- Chordal Graphs
- Split Graphs
- Cobipartite Graphs
- Cographs
- Chain Graphs
- Conclusions
- References
- Randomized Group Testing Both Query-Optimal and Minimal Adaptive
- Introduction
- Minimal Adaptive Group Testing Close to the Entropy Lower Bound
- Linear versus Sublinear Growth of the Defectives
- References
- Complexity of Model Checking for Modal Dependence Logic
- Introduction
- Modal Dependence Logic
- Unbounded Arity Fragments
- Bounded Arity Fragments
- Conclusion
- References
- Multitape NFA: Weak Synchronization of the Input Heads
- Introduction
- Preliminaries
- 2-Ambiguous Multitape NFA
- Unambiguous Multitape NFA
- Multitape NFA on ABO-Bounded Inputs
- Multitape NFA on Unary Inputs
- Synchronizability
- Weakly Synchronized Regular Languages
- Weakly Synchronized NFA on Unary Inputs
- Conclusion
- References
- Visibly Pushdown Transducers with Look-Ahead
- Introduction
- Visibly Pushdown Languages and Transductions
- VPT with Visibly Pushdown Look-Ahead
- Functional VPT and VPTla
- Decision Problems
- References
- A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators
- Introduction
- Preliminaries
- Space Bounded Turing Machines
- The Circuit Model
- Separators and Segregators
- Boolean Circuits with Small Segregators or Separators
- Finding Minimum Size Segregators in Small Space
- Segregators of Directed Acyclic Graphs
- Segregators of Uniform Circuits
- Generating the Simulating Circuits in Small Space
- Circuit Value Problem
- References
- Consistent Consequence for Boolean Equation Systems
- Introduction
- Preliminaries
- Consistent Consequence
- Consistent Consequence Generalises Direct Simulation on Parity Games
- The Proof System c
- Application
- Future Work
- References
- 4-Coloring H-Free Graphs When H Is Small
- Introduction
- Preliminaries
- The Algorithm
- References
- Computing q-Gram Non-overlapping Frequencies on SLP Compressed Texts
- Introduction
- Preliminaries
- Notation
- Occurrences and Frequencies
- Straight Line Programs
- q-gram Non-overlapping Frequencies on Compressed String
- Key Ideas
- Computing Longest Overlapping Covers
- Largest Left-Priority and Smallest Right-Priority Occurrences
- Counting Non-overlapping Occurrences in Longest Overlapping Covers
- Main Result
- Conclusion
- References
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- Introduction
- Main Algorithm for MKP
- Pre-assignment and LP Relaxation
- High Profit Items
- Medium Profit Items
- Linear Program Relaxation
- New Rounding Strategy
- Packing and Shifting Arguments
- References
- Counting Maximal Independent Sets in Subcubic Graphs
- Introduction
- Preliminaries
- The Algorithm
- Complexity
- References
- Iterated Hairpin Completions of Non-crossing Words
- Introduction
- Preliminaries
- Hairpin Completion
- Non-crossing Words and Their Properties
- a-Prefixes and 1mu-1mu-1mu1mu-Suffixes
- The a-Index
- Iterated Hairpin Completion of Non-crossing Words
- References
- On the Approximation Ratio of the Path Matching Christofides Algorithm
- Introduction
- The PMCA for the Traveling Salesman Problem
- The PMCA for the Hamiltonian Path Problem
- References
- Parikh's Theorem and Descriptional Complexity
- Introduction
- Preliminaries
- The Bounded Case
- The General Case
- References
- A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
- Introduction
- A Reduction of APSP to Mixed Matrix Products
- The APSP Problem
- Mixed Matrix Products
- The Reduction
- Fast Computation of the Mixed Products for Clustered Data
- Approximate Minimum Spanning Tree in High Dimensional Space
- The Algorithm for Mixed Matrix Product
- Main Results
- APSP in Vertex-Weighted Uniform Disk Graphs of Bounded Density
- Final Remarks
- References
- The Complexity of Small Universal Turing Machines: A Survey
- Introduction
- Time and Size Efficiency of Universal Machines
- Non-standard Universal Turing Machines: Time Efficiency and Program Size
- Weak Universality and Rule 110
- Other Non-standard Universal Turing Machines
- Restricted Universal Turing Machines
- Universal Turing Machines with Multidimensional Tapes: Time Efficiency and Program Size
- Termination of a Computation
- Busy Beavers
- Further Work
- References
- A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- Introduction
- The Richness Condition
- Definition of Partition Class
- The Block Structure below Provided That p3(µ)&1/12
- The Recursion
- Conclusion
- References
- Complete Problem for Perfect Zero-Knowledge Quantum Proof
- Introduction
- Preliminaries
- Quantum Circuit Model
- Efficiently Preparable Quantum State
- Perfect Zero-Knowledge Quantum Interactive Proof
- Perfect Zero-Knowledge Quantum Non-interactive Proof
- Complete Problems
- The Completeness Theorem
- Conclusion
- References
- An Algorithm for Probabilistic Alternating Simulation
- Introduction
- Preliminaries
- Solving GCPP in Probabilistic Game Structures
- A Decision Procedure for PA-I-Simulation
- Conclusion
- References
- Software and Web Engineering
- Towards a Smart, Self-scaling Cooperative Web Cache
- Introduction
- Analysis and Design of the CWC
- Case Study
- Client Evaluation in Homogeneous Network
- Client Evaluation in Heterogeneous Network
- Server Load Evaluation
- Server Delay Dependency
- Resilience to Abrupt Departure
- Related Work
- Conclusion
- References
- Named Entity Disambiguation Based on Explicit Semantics
- Introduction
- Related Work
- Semantic Ambiguity
- Large-Scale Disambiguation
- Formal Definition
- Entity Disambiguation Using Wikipedia
- Dataset Structure
- Semantic Space
- Entity Identification
- Document Transformation
- Candidate Meanings
- Ranking
- Evaluation
- Conclusion and Future Work
- References
- Design Pattern Support Based on the Source Code Annotations and Feature Models
- Introduction
- Related Work
- Open Problems and Our Ideas
- Method of Design Pattern Support in the Source Code
- Proposal of Annotation for Design Patterns
- Support of Design Pattern Instantiation and Evolution
- Realization
- Elimination of Manual Annotation of the Source Code
- Evaluation
- Conclusion and Future Work
- References
- On the Formalization of UML Activities for Component-Based Protocol Design Specifications
- Motivation
- cTLA - Compositional Temporal Logic of Actions
- Formalizing the Semantics of UML Activity Diagrams
- Semantics Definition for Activity Nodes
- Functional Semantics
- Related Work
- Final Remarks
- References
- Tree Based Domain-Specific Mapping Languages
- Introduction
- Basic Principles of Mapping Language Family
- Proposed Mapping Language for MDSD
- Basics of MALA4MDSD
- More Advanced Mapping Elements
- Mapping and Transformation Comparison
- Mapping Language Definition
- Related Work
- Conclusions
- References
- RESTGroups for Resilient Web Services
- Introduction
- RESTGroups Design and Service Replication
- System Design
- Service Replication
- Statelessness
- RESTGroups API Calls
- Connecting to the Server
- Sending Messages
- Reception of Messages
- Related Work
- Conclusion
- References
- Leveraging Microblogs for Resource Ranking
- Introduction
- Related Work
- Microblog-Based Resource Ranking
- TweetRank Computation
- Evaluation
- Dataset
- Comparison with YouTube User Rank
- Sorting Search Results with TweetRank
- Conclusions
- References
- Inner Architecture of a Social Networking System
- Introduction
- The Wall
- Entity
- Analysis
- Existing Social Networks
- Technological Requirements
- Functional Requirements
- Used Technologies
- Architecture and Design
- Inner Architecture
- Data Model
- Storing Data
- Wall and News Feed
- Implementation
- Case Study
- Implementation
- Testing
- Conclusion
- References
- State Coverage: Software Validation Metrics beyond Code Coverage
- Introduction
- State Coverage
- Definition
- Object Insensitive State Coverage
- Object Sensitive State Coverage
- Evaluation
- General Results
- Detailed Evaluation of DSA
- Related Work
- Conclusion and Future Work
- References
- Cryptography, Security, and Verification
- Factorization for Component-Interaction Automata
- Introduction
- Preliminaries
- The Factorization Problem
- From CI Automata to FSM and Back
- The Algorithm
- Conclusion and Future Work
- References
- Optimizing Segment Based Document Protection
- Introduction
- Segment Based Document Protection
- Hierarchical Key Structures and Key Derivation Techniques
- Document Encoding and Problem Statement
- Tree-Based Key Derivation
- Sequential Key Derivation
- OpenProblems
- References
- Securing the Future - An Information Flow Analysis of a Distributed OO Language
- Introduction
- The Programming Language
- Syntax
- Operational Semantics
- Type System for Non-interference
- Types
- Non-interference
- Related Work
- Conclusions
- References
- Improving Watermark Resistance against Removal Attacks Using Orthogonal Wavelet Adaptation
- Introduction
- Orthogonal Wavelet Filter Parametrization
- Image Watermarking in the Wavelet Transform Domain
- Watermarked Image Fidelity
- Improving Watermark Attack Resistance
- Experimental Results
- Scope of the Proposed Method
- Conclusions
- References
- Artificial Intelligence
- MAK? - A System for Modelling, Optimising, and Analyzing Production in Small and Medium Enterprises
- Introduction
- The Problem
- Why CP?
- How CP?
- The Core Model
- Search Strategy
- Added Value of CP
- References
- Knowledge Compilation with Empowerment
- Introduction
- Preliminaries
- Empowering Implicates
- Empowerment
- Finding Empowering Implicates Using QBF
- Compilation by Iterative Empowerment
- Compilation Sequences
- Clause Deprecation
- Length-Increasing Iterative Empowerment
- Minimality
- Iterative Empowerment versus Prime Implicate Saturation
- Previous Compilation Schemes
- Iterative Empowerment versus Prime Implicates
- Iterative Empowerment versus Merge Resolution
- Conclusion and Perspectives
- References
- Cost-Sensitive Classification with Unconstrained Influence Diagrams
- Introduction
- Problem Statement
- Related Work
- Proposed Method
- Unconstrained Influence Diagrams
- Classification UID
- Classification of Samples
- Full-Powered Bayesian Inference
- Remarks
- Experiments
- Conclusions and Future Work
- References
- Modeling and Predicting Students Problem Solving Times
- Introduction
- Modeling Problem Solving Times
- Summary of Item Response Theory
- Problem Solving Times
- Specific Assumptions and Model
- Group Invariance
- Parameter Estimation
- Estimating Ability
- Estimating Problem Parameters
- Joint Estimation
- Application and Evaluation
- Problem Solving Tutor
- Evaluation of Predictions
- Insight Gained from Parameter Values
- Conclusions and Future Work
- References
- Generic Heuristic Approach to General Game Playing
- Introduction
- The Class of Considered Games
- Game Description Language
- State-of-the-Art
- Automatic Construction of the Evaluation Function
- Selection Phase
- Construction of a Heuristic Function
- The Use of the Heuristic Function
- Empirical Results
- Conclusion
- References
- The SiMoL Modeling Language for Simulation and (Re-)Configuration
- Introduction
- Related Research
- An Example
- SiMoL Definition
- SiMoL Syntax
- SiMoL Inheritance Mechanism
- Semantics of SiMoL
- Re-Configuration
- Conclusion
- References
- Author Index
