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

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
An O * (1.84 k ) Parameterized Algorithm for the Multiterminal Cut Problem....Pages 84-94
Expressivity of Time-Varying Graphs....Pages 95-106
Parameterized Complexity of Weak Odd Domination Problems....Pages 107-120
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree....Pages 121-132
A Formal Framework for Property-Driven Obfuscation Strategies....Pages 133-144
Online Parallel Scheduling of Non-uniform Tasks: Trading Failures for Energy....Pages 145-158
Cancellation-Free Circuits in Unbounded and Bounded Depth....Pages 159-170
The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design....Pages 171-182
On Independence Domination....Pages 183-194
Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks....Pages 195-209
New Sequential and Parallel Algorithms for Computing the β -Spectrum....Pages 210-224
Approximation Algorithms for the Antenna Orientation Problem....Pages 225-235
Improved Approximation Algorithms for Constrained Fault-Tolerant Resource Allocation....Pages 236-247
An Axiomatization of the Theory of Generalized Ultrametric Semilattices of Linear Signals....Pages 248-258
On the Structure of Equilibria in Basic Network Formation....Pages 259-270
Domination Analysis of Algorithms for Bipartite Boolean Quadratic Programs....Pages 271-282
Groups with a Recursively Enumerable Irreducible Word Problem....Pages 283-292
Real-Time Vector Automata....Pages 293-304
Guarding Thin Orthogonal Polygons Is Hard....Pages 305-316
Back Matter....Pages -