Vincent Cremet, François Garillot, Sergueï Lenglet, Martin Odersky (auth.), Rastislav Královič, Paweł Urzyczyn (eds.)3540377913, 9783540377917
The 62 revised full papers presented together with the full papers or abstracts of 7 invited talks were carefully reviewed and selected from 174 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithms and data structures, to complexity, automata, semantics, logic, formal specifications, models of computation, concurrency theory, computational geometry, parallel and distributed computing, networks, bioinformatics, quantum computing, cryptography, knowledge-based systems, and artificial intelligence.
Table of contents :
Front Matter….Pages –
A Core Calculus for Scala Type Checking….Pages 1-23
Tree Exploration with an Oracle….Pages 24-37
Distributed Data Structures: A Survey on Informative Labeling Schemes….Pages 38-38
From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductions….Pages 39-57
The Structure of Tractable Constraint Satisfaction Problems….Pages 58-72
On the Representation of Kleene Algebras with Tests….Pages 73-83
From Three Ideas in TCS to Three Applications in Bioinformatics….Pages 84-85
Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles….Pages 86-97
Approximate Shortest Path Queries on Weighted Polyhedral Surfaces….Pages 98-109
A Unified Construction of the Glushkov, Follow, and Antimirov Automata….Pages 110-121
Algebraic Characterizations of Unitary Linear Quantum Cellular Automata….Pages 122-133
A Polynomial Time Nilpotence Test for Galois Groups and Related Results….Pages 134-145
The Multiparty Communication Complexity of Exact- T : Improved Bounds and New Problems….Pages 146-156
Crochemore Factorization of Sturmian and Other Infinite Words….Pages 157-166
Equations on Partial Words….Pages 167-178
Concrete Multiplicative Complexity of Symmetric Functions….Pages 179-189
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures….Pages 190-201
Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities….Pages 202-213
The Kleene Equality for Graphs….Pages 214-225
On the Repetition Threshold for Large Alphabets….Pages 226-237
Improved Parameterized Upper Bounds for Vertex Cover….Pages 238-249
On Comparing Sums of Square Roots of Small Integers….Pages 250-255
A Combinatorial Approach to Collapsing Words….Pages 256-266
Optimal Linear Arrangement of Interval Graphs….Pages 267-279
The Lempel-Ziv Complexity of Fixed Points of Morphisms….Pages 280-291
Partially Commutative Inverse Monoids….Pages 292-304
Learning Bayesian Networks Does Not Have to Be NP-Hard….Pages 305-314
Lower Bounds for the Transition Complexity of NFAs….Pages 315-326
Smart Robot Teams Exploring Sparse Trees….Pages 327-338
k -Sets of Convex Inclusion Chains of Planar Point Sets….Pages 339-350
Toward the Eigenvalue Power Law….Pages 351-362
Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves….Pages 363-374
Very Sparse Leaf Languages….Pages 375-386
On the Correlation Between Parity and Modular Polynomials….Pages 387-398
Optimally Fast Data Gathering in Sensor Networks….Pages 399-411
Magic Numbers in the State Hierarchy of Finite Automata….Pages 412-423
Online Single Machine Batch Scheduling….Pages 424-435
Machines that Can Output Empty Words….Pages 436-446
Completeness of Global Evaluation Logic….Pages 447-458
NOF-Multiparty Information Complexity Bounds for Pointer Jumping….Pages 459-470
Dimension Characterizations of Complexity Classes….Pages 471-479
Approximation Algorithms and Hardness Results for Labeled Connectivity Problems….Pages 480-491
An Expressive Temporal Logic for Real Time….Pages 492-504
On Matroid Representability and Minor Problems….Pages 505-516
Non-cooperative Tree Creation….Pages 517-527
Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners….Pages 528-539
Reductions for Monotone Boolean Circuits….Pages 540-548
Generalised Integer Programming Based on Logically Defined Relations….Pages 549-560
Probabilistic Length-Reducing Automata….Pages 561-572
Sorting Long Sequences in a Single Hop Radio Network….Pages 573-583
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture….Pages 584-595
Valiant’s Model: From Exponential Sums to Exponential Products….Pages 596-607
A Reachability Algorithm for General Petri Nets Based on Transition Invariants….Pages 608-621
Approximability of Bounded Occurrence Max Ones….Pages 622-633
Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability….Pages 634-645
Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes….Pages 646-657
Quantum Weakly Nondeterministic Communication Complexity….Pages 658-669
Minimal Chordal Sense of Direction and Circulant Graphs….Pages 670-680
Querying and Embedding Compressed Texts….Pages 681-692
Lempel-Ziv Dimension for Lempel-Ziv Compression….Pages 693-703
Characterizing Valiant’s Algebraic Complexity Classes….Pages 704-716
The Price of Defense….Pages 717-728
The Data Complexity of MDatalog in Basic Modal Logics….Pages 729-740
The Complexity of Counting Functions with Easy Decision Version….Pages 741-752
On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model….Pages 753-764
Constrained Minimum Enclosing Circle with Center on a Query Line Segment….Pages 765-776
Hierarchical Unambiguity….Pages 777-788
An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture….Pages 789-800
On Genome Evolution with Innovation….Pages 801-811
Back Matter….Pages –
Reviews
There are no reviews yet.