Topics in Theoretical Computer Science
The First IFIP WG 1.8 International Conference, TTCS 2015, Tehran, Iran, August 26-28, 2015, Revised Selected Papers
Published on 8. January 2016
XV, 179 pages
978-3-319-28678-5 (ISBN)
Description
This book constitutes the thoroughly refereed post-conference proceedings of the First IFIP WG 1.8 International Conference on Topics in Theoretical Computer Science, held in Tehran, Iran, in August 2015.
The 10 full papers presented together with 3 invited talks were carefully reviewed and selected from 48 submissions. The papers feature novel and high-quality research in all areas of theoretical computer science.More details
Other editions
Additional editions
Mohammed Taghi Hajiaghayi | Mohammad Reza Mousavi
Topics in Theoretical Computer Science
The First IFIP WG 1.8 International Conference, TTCS 2015, Tehran, Iran, August 26-28, 2015, Revised Selected Papers
Book
01/2016
Springer
€53.49
Shipment within 10-15 days
Content
- Intro
- Preface
- Organization
- Abstracts of Invited Talks
- New Directions in Parameterized Algorithmics
- Distributional Sentence Entailment Using Density Matrices
- On Symmetric and Choiceless Computation
- Contents
- Distributional Sentence Entailment Using Density Matrices
- 1 Introduction
- 2 Background
- 3 Density Matrices as Elements of a Compact Closed Category
- 4 Using Density Matrices to Model Meaning
- 5 From Meanings of Words to the Meanings of Sentences Passage
- 6 Truth Theoretic Examples
- 6.1 Entailment Between Nouns
- 6.2 Entailment Between Sentences in One Dimensional Truth Theoretic Space
- 6.3 Entailment Between Sentences in Two Dimensional Truth Theoretic Space
- 7 Distributional Examples
- 7.1 Entailment Between Nouns
- 7.2 Entailment Between Sentences
- 8 Conclusion and Future Work
- References
- On Symmetric and Choiceless Computation
- References
- Robots' Cooperation for Finding a Target in Streets
- 1 Introduction
- 2 Related Works
- 3 The Sensing Model and Communications
- 3.1 Gap Sensor
- 3.2 Communications
- 3.3 Motion Primitive
- 4 Preliminaries
- 5 Algorithm
- 5.1 Critical Events
- 5.2 Message Events
- 5.3 Analysis
- 6 Conclusion
- References
- Some Properties of Continuous Yao Graph
- 1 Introduction
- 2 cY() is Fault-Tolerant
- 3 cY() is Not Self-approaching
- 4 Concluding Remarks
- References
- Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
- 1 Introduction
- 1.1 Preliminaries
- 1.2 Non-crossing Structures in the Plane
- 1.3 Our Contributions
- 2 Plane Geodesic Hamiltonian Cycles
- 2.1 Sweep-Path Algorithm
- 2.2 Plane Geodesic Hamiltonian Cycles
- 3 Plane Geodesic Trees
- 4 Balanced Geodesics
- 5 Plane Colored Geodesic Matchings
- References
- Visibility Graphs of Anchor Polygons
- 1 Introduction
- 2 Preliminaries and Definitions
- 2.1 Spiral Polygons
- 2.2 Definitions
- 2.3 Basic Facts
- 3 Recognizing Algorithm: Determining Joint Vertices
- 3.1 Finding Joint Vertices B and C
- 3.2 Determining Joint Vertex A
- 4 Reconstruction Algorithm
- 4.1 Anchor Polygon Decomposition
- 4.2 Reconstructing Sub-polygons
- 5 Complexity Analysis
- References
- Automating the Verification of Realtime Observers Using Probes and the Modal mu-calculus
- 1 Introduction
- 2 The Fiacre Language
- 3 Timed Traces and First-Order Formulas Over Traces
- 4 Visual Verification of Observers
- 5 Automating the Visual Verification Method
- 6 Related Work and Conclusion
- References
- Minimizing Walking Length in Map Matching
- 1 Introduction
- 2 Preliminaries and Definitions
- 3 Algorithm
- 4 Improvement
- 5 Weighted Non-planar Graphs
- 6 Conclusion
- References
- Rainbow Domination and Related Problems on Some Classes of Perfect Graphs
- 1 Introduction
- 2 k-Rainbow Domination on Cographs
- 3 Weak {k}-L-Domination on Trivially Perfect Graphs
- 4 2-Rainbow Domination of Interval Graphs
- 5 `39`42`"613A``45`47`"603ANP-Completeness for Splitgraphs
- References
- Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width
- 1 Introduction
- 2 Preliminaries
- 2.1 MSOL-Ising Polynomials
- 2.2 MSOL-Ising Polynomials vs MSOL-Polynomials
- 3 Main Result
- 3.1 Runtime
- 4 Conclusion
- References
- Infinite Subgame Perfect Equilibrium in the Hausdorff Difference Hierarchy
- 1 Introduction
- 2 Technical Background
- 3 Many Players with Linearly Ordered Preferences
- 4 Two Players with Strict Weak Order Preferences
- References
- Deterministic Algorithm for 1-Median 1-Center Two-Objective Optimization Problem
- 1 Introduction
- 2 One Dimensional
- 3 Two Dimensional
- 3.1 1-Median Objective
- 3.2 1-Center Objective
- 3.3 Pareto Optimal Solutions
- 4 Conclusion and Future Work
- References
- Author Index
