Ebook: Fundamentals of Computation Theory: 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings

This book constitutes the refereed proceedings of the 19th International Symposium on Fundamentals of Computation Theory, FCT 2013, held in Liverpool, UK, in August 2013. The 29 papers (26 full papers and 3 invited papers) were carefully reviewed and selected from 58 submissions. The papers cover the following topics: algorithms, formal methods, and emerging fields.
Content:
Front Matter....Pages -
Together or Separate? Algorithmic Aggregation Problems....Pages 1-1
Decision Problems for Linear Recurrence Sequences....Pages 2-2
Randomized Distributed Decision (Invited Lecture Abstract)....Pages 3-3
On the Complexity of Finding a Largest Common Subtree of Bounded Degree....Pages 4-15
On the Isomorphism Problem for Decision Trees and Decision Lists....Pages 16-27
Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree....Pages 28-39
One Alternation Can Be More Powerful Than Randomization in Small and Fast Two-Way Finite Automata....Pages 40-47
Efficient Sampling of Non-strict Turnstile Data Streams....Pages 48-59
The Frequent Items Problem in Online Streaming under Various Performance Measures....Pages 60-71
On the Average Size of Glushkov and Equation Automata for KAT Expressions....Pages 72-83
Expressivity of Time-Varying Graphs....Pages 84-94
Parameterized Complexity of Weak Odd Domination Problems....Pages 95-106
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree....Pages 107-120
A Formal Framework for Property-Driven Obfuscation Strategies....Pages 121-132
Online Parallel Scheduling of Non-uniform Tasks: Trading Failures for Energy....Pages 133-144
Cancellation-Free Circuits in Unbounded and Bounded Depth....Pages 145-158
The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design....Pages 159-170
On Independence Domination....Pages 171-182
Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks....Pages 183-194
New Sequential and Parallel Algorithms for Computing the β-Spectrum....Pages 195-209
Approximation Algorithms for the Antenna Orientation Problem....Pages 210-224
Improved Approximation Algorithms for Constrained Fault-Tolerant Resource Allocation....Pages 225-235
An Axiomatization of the Theory of Generalized Ultrametric Semilattices of Linear Signals....Pages 236-247
On the Structure of Equilibria in Basic Network Formation....Pages 248-258
Domination Analysis of Algorithms for Bipartite Boolean Quadratic Programs....Pages 259-270
Groups with a Recursively Enumerable Irreducible Word Problem....Pages 271-282
Real-Time Vector Automata....Pages 283-292
Guarding Thin Orthogonal Polygons Is Hard....Pages 293-304
Back Matter....Pages 305-316
....Pages -