STACS 2009: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, 26-28 February 2009 (Leibniz International Proceedings in Informatics - LIPIcs)

FOREWORD......Page 3
Contributed papers......Page 11
Introduction......Page 15
1.1. Algorithm A......Page 17
1.2. Algorithm B......Page 18
1.3. Algorithm C......Page 19
2. Implementation details......Page 20
3. Experiments......Page 21
3.1. Nodes per host distribution......Page 22
3.2. PageRank bias......Page 24
3.3. Outdegree distribution......Page 26
3.4. Top level domain (TLD) distribution......Page 28
3.5. Document content length distribution......Page 29
4. Comparison of techniques......Page 31
References......Page 32
PROFINITE METHODS IN AUTOMATA THEORY......Page 33
1. Metric spaces......Page 34
2.2. Profinite metrics......Page 35
3. Equational definitions of varieties......Page 37
4. Recognizable languages and clopen sets......Page 38
5. Equational characterization of languages......Page 40
5.1. Lattices of languages......Page 41
5.2. Lattices of languages closed under quotient......Page 43
5.3. Varieties of languages......Page 44
6. Pro-V uniformities......Page 46
6.1. Progroup topology......Page 48
6.2. Pro-p topology......Page 49
7. Conclusion......Page 50
References......Page 51
1. Introduction......Page 65
1.1. Motivation......Page 66
1.3. Related work......Page 67
2. Algorithm for a shortest s-t path......Page 68
2.2. Constructing the tree......Page 70
3.1. Justifying the graph modi cation......Page 71
3.2. Justifying the tree construction......Page 72
3.3. Analyzing time and space requirement......Page 73
4. Extensions......Page 74
Acknowledgment......Page 75
References......Page 76
1. Introduction......Page 77
1.1. Our Contributions......Page 78
2. Preliminaries......Page 79
2.1. Lattices......Page 80
3. Construction......Page 82
3.1. Parity Check and Hermite Normal Form......Page 83
3.2. The Block Structure......Page 84
3.3. Building the Blocks......Page 85
3.4. Analysis......Page 86
References......Page 87
Introduction......Page 101
1.2. Dynamical point of view : subshifts......Page 102
2.2. Local transformations......Page 103
2.3. Transformation on the group of the action......Page 104
3.2. A framework for Turing machines......Page 105
3.3. A 2-dimensional so c subshift......Page 106
4.1. A semi-order on languages......Page 107
4.2. Closure theorem:......Page 108
References......Page 112
1. Introduction......Page 113
2. Previous Work......Page 114
3.1. Wavelet Tree on Runs......Page 115
3.2. Stricter Runs......Page 117
3.3. Shuffled Sequences......Page 118
4.1. Inverted Indexes......Page 119
4.3. Iterated Permutation......Page 121
5. Conclusion......Page 122
References......Page 123
1. Introduction......Page 125
2.1. Finite automata......Page 126
2.2. Myhill-Nerode equivalence......Page 127
2.3. Moore’s state minimization algorithm......Page 128
2.4. Probabilistic model......Page 129
3. Main result......Page 130
4. Tight bound for unary automata......Page 134
5.2. Possibly incomplete automata......Page 135
References......Page 136
1. Introduction......Page 137
2.2. Overview of Proofs......Page 142
3.1. Fourier Analysis and Green’s Regularity Lemma
......Page 144
3.2. Testability of Complexity 1 Matroid Freeness......Page 145
5. Infinitely many Monotone Properties......Page 146
References......Page 147
1. Introduction......Page 149
2. Computable upper bounds of Kolmogorov complexity......Page 150
3.1. The Miller-Yu theorem......Page 153
3.2. A “no-gap” theorem for randomness......Page 154
4. Solovay functions and triviality notions......Page 157
References......Page 160
1. Introduction......Page 161
2. The automaton......Page 163
3. The logic......Page 164
4. Weak bounding logic is captured by deterministic max-automata......Page 165
4.1. Weak existential quantification......Page 166
4.2. Unbounding quantification......Page 168
5. Problems with nondeterminism......Page 170
References......Page 172
1. Introduction......Page 173
2. Basics......Page 174
3. Structure Theorem......Page 175
3.1. Mortar Graph......Page 176
3.2. Structural properties......Page 177
4. Algorithm......Page 179
5.1. Preprocessing the Input Graph......Page 181
5.3. Proof of Theorem 3.3......Page 183
References......Page 184
Introduction and definitions......Page 197
1. Families of CA with Local Symmetries......Page 198
2. Simulations and Universality......Page 200
3.2. Density of monotone properties among symmetric family......Page 201
4. Encodings......Page 205
6. Open Problems and Future Work......Page 207
References......Page 208
1. Introduction......Page 221
2. Preliminaries......Page 224
3.2. Randomized codes......Page 225
3.3. Quantum codes......Page 227
4. Pauli decoding from disjoint subsets......Page 228
4.2. Pauli decoding......Page 229
6. Conclusion and open problems......Page 231
References......Page 232
1. Introduction......Page 257
1.1. Related results......Page 259
1.2. Formal Problem Definition and Notations......Page 260
2. An O( 3)-competitive Algorithm......Page 261
3. Lower Bounds......Page 264
4. Conclusion......Page 265
References......Page 266
1.1. Seriation problem
......Page 267
1.4. Our result and techniques
......Page 268
2. Preliminary results......Page 269
3.2. Pairwise admissible holes
......Page 270
4.1. Blocks, cells, and clusters
......Page 271
4.2. Partitioning Xij into X and X +......Page 272
4.4. Defining the total order on Xi
......Page 276
5. The algorithm and its performance guarantee......Page 277
References......Page 278
1. Introduction......Page 279
2. Preliminaries and Basic Facts......Page 282
3. A Vertex Sampling Problem......Page 284
4. Sampling Rational Points on Varieties......Page 286
5. Concluding Remarks......Page 289
References......Page 290
1. Introduction......Page 291
2.1. Preliminaries and definitions......Page 293
2.2. Properties......Page 294
3. Testing an integer table......Page 295
3.1. Algorithm......Page 296
3.2. Correctness of the algorithm......Page 297
4.1. Linear running time......Page 298
4.2. Contiguous letters......Page 299
4.3. Alphabet size......Page 300
References......Page 302
THE PRICE OF ANARCHY IN COOPERATIVE NETWORK CREATION GAMES......Page 303
1. Introduction......Page 304
2.2. Cooperative Model......Page 307
3. Preliminaries......Page 308
4. Cooperative Version in Complete Graphs......Page 309
5. Cooperative Version in General Graphs......Page 311
6. Unilateral Version in General Graphs......Page 312
References......Page 313
1. Introduction......Page 315
1.1. Our results......Page 318
1.2. Related work......Page 319
2.1. Noiseless case: the BMRV data structure for Membership......Page 320
2.3. Noisy case: p > 1 probes......Page 321
3.1. Noiseless case......Page 323
3.2. Noisy case......Page 324
4. Future work......Page 325
References......Page 326
1. Introduction......Page 327
2. Preliminaries......Page 328
3. The alphabetic topology and polynomials......Page 329
4. Recognizability by finite monoids......Page 331
5. The fragment  2......Page 332
6. Two variable  rst-order logic......Page 333
8. The fragment  2 =  2 n  2......Page 335
10. Outlook and open problems......Page 337
References......Page 338
Introduction......Page 339
1.1. Symbolic Dynamics......Page 340
1.2. Cellular Automata......Page 341
2. Properties of limit sets......Page 343
3. Undecidable properties of limit set dynamics......Page 345
4. Concluding remarks......Page 348
References......Page 349
1. Introduction......Page 351
2. The optimal algorithm......Page 355
3. Reductions and linear programs......Page 357
3.1. Known sum of processing times
......Page 358
3.3. Non-increasing processing times, decr......Page 361
References......Page 362
1. Introduction......Page 363
1.2. Our results and outline of the paper......Page 364
2. Preliminaries......Page 365
3. Left-guarding and totally balanced matrices......Page 366
3.1. Uniform left-guarding......Page 367
4. A 2-approximation for one-sided guarding......Page 368
4.1. Partial covering......Page 369
5.1. The continuous case......Page 370
5.2. The discrete case......Page 371
Acknowledgements......Page 372
References......Page 373
1. Introduction......Page 375
2. Notations, Definitions and Preliminaries......Page 378
3.1. Upper Bound on R(G)......Page 380
4.1. Sparse Graphs
......Page 382
4.2. Dense Graphs......Page 383
4.3. Discussion......Page 384
References......Page 385
ECONOMICAL CACHING......Page 387
1.1. Our Results......Page 388
1.2. Previous Work......Page 389
2.1. The Optimal O ine Algorithm......Page 390
2.2. The Optimal Online Algorithm......Page 391
2.3. Algorithm for Larger Storage Capacities......Page 393
3.1. General Lower Bound
......Page 395
3.2. Lower Bound for Algorithms with Fixed Buying Functions
......Page 397
References......Page 398
COMPUTING GRAPH ROOTS WITHOUT SHORT CYCLES......Page 399
1. Introduction......Page 400
2. Squares of graphs with girth at least seven......Page 401
3. Squares of graphs with girth at least six......Page 404
3.1. Square root with a speci ed neighborhood......Page 405
4. Squares of graphs with girth four......Page 407
5. Conclusion and open problems......Page 408
References......Page 409
A GENERALIZATION OF NEMHAUSER AND TROTTER’S LOCAL OPTIMIZATION THEOREM......Page 411
1. Introduction......Page 412
2. Preliminaries......Page 414
3. A Local Optimization Algorithm for Bounded-Degree Deletion......Page 415
3.1. The Algorithm......Page 416
3.2. Running Time and Correctness......Page 418
4. Conclusion......Page 421
References......Page 422
1. Introduction......Page 423
2. Preliminaries......Page 425
3. Reduction Rules for Rooted k-Leaf Out-Branching......Page 426
4.1. Bounding the Number of Entry and Exit Points of a Path......Page 428
4.2. Bounding the Length of a Path: On Paths Through Nice Forests......Page 430
5. Kernelization Lower Bounds......Page 432
6. Conclusion and Discussions......Page 433
References......Page 434
1. Introduction......Page 447
2. Definitions and preliminaries......Page 449
3. When hypertree width is sandwiched by treewidth......Page 452
4. Hypergraphs with H-minor-free incidence graphs......Page 454
References......Page 458
1. Introduction......Page 459
2. A Simple(r) Linear-Time Suÿx Selection Algorithm......Page 461
3. Cache-Aware Sparse Suÿx Selection......Page 465
4. Optimal Cache-Aware Suÿx Selection......Page 467
4.1. Finding pivots and the key suffixes
......Page 468
4.2. Discarding key suffixes......Page 469
References......Page 470
1. Introduction......Page 471
2. Computability......Page 472
2.1. Computable metric spaces......Page 473
3. Computable Probability Spaces......Page 474
3.1. Randomness and typicality......Page 478
3.2. Dynamical systems and typicality......Page 479
3.3. Proof of the main result......Page 480
References......Page 482
1. Introduction......Page 483
2. Definitions......Page 485
2.1. Dynamic Languages and Complexity Classes......Page 486
2.2. Extended Dynamic Programs......Page 487
3. Dynamic Complexity of Regular Languages......Page 488
4. Dynamic Complexity of Context-free Languages......Page 490
5. Variations......Page 491
6. Beyond Formal Languages......Page 492
7. Conclusion......Page 493
References......Page 494
1. Introduction......Page 495
2. Hadamard matrices......Page 500
3. The General Case......Page 505
References......Page 506
1. Introduction......Page 507
1.1. Our Result......Page 508
2.1. Notation......Page 509
2.2. Information Theory......Page 510
2.3. Information Complexity......Page 511
3. The Information Complexity of ANDk......Page 512
3.1. Some Basic Observations......Page 513
3.2. Main Idea of the Proof......Page 514
References......Page 518
MORE HASTE, LESS WASTE: LOWERING THE REDUNDANCY IN FULLY INDEXABLE DICTIONARIES......Page 519
1. Introduction......Page 520
2. Elias-Fano Revisited......Page 522
3. Basic Components and Main Result......Page 524
4.1. Overview of our recursive dictionary......Page 525
4.2. Multiranking......Page 526
4.3. Completing the puzzle......Page 527
References......Page 529
A UNIFIED ALGORITHM FOR ACCELERATING EDIT-DISTANCE COMPUTATION VIA TEXT-COMPRESSION......Page 531
1. Introduction......Page 532
1.1. Straight-line programs......Page 533
1.3. Related Work......Page 534
2. The DIST Table......Page 535
3. Acceleration via Straight-Line Programs......Page 536
4. Constructing an xy-partition......Page 538
5. Improvement for Rational Scoring Functions......Page 540
References......Page 541
1. Introduction......Page 555
2. A Proof Sketch......Page 557
3. From Automata to Communication......Page 558
4. The Communication Problem......Page 561
5. From Nondeterminism to Determinism......Page 562
6. A Hierarchy for Polynomial Ambiguity......Page 564
References......Page 566
1. Introduction......Page 579
2. Equations over sets of numbers......Page 581
3. Encoding of sets......Page 582
4. Simulating operations......Page 585
5. Simulating a system of equations......Page 587
6. Systems with finite constants......Page 589
References......Page 590
1. Introduction......Page 591
2.2. Min-Plus Automata......Page 592
3.1. Metatransitions......Page 593
3.2. The Semigroup of Metatransitions of an Automaton......Page 594
3.4. Stabilization......Page 595
3.5. Main Results, Conclusions, and Open Questions......Page 596
4. Necessity......Page 598
5. Suÿciency......Page 600
References......Page 602
1. Introduction......Page 603
2. Preliminaries......Page 605
3. Polynomial kernelization for MIN F+ 1......Page 607
4. Polynomial kernelization for MAX NP......Page 610
Acknowledgement......Page 613
References......Page 614
1. Introduction......Page 627
2. Preliminaries......Page 629
3. Computing a Standard Decomposition......Page 630
4.1. Automorphisms of an abelian group......Page 633
4.2. Testing conjugacy in R(A)......Page 634
5. Our Algorithm......Page 636
Acknowledgments......Page 637
References......Page 638
1. Multi-Criteria Traveling Salesman Problem......Page 639
3. Decompositions......Page 642
4.1. Multi-Criteria Max-ATSP......Page 644
4.2. Multi-Criteria Max-STSP......Page 646
5. Deterministic Approximations for 2-C-Max-STSP......Page 647
6. Approximation Algorithm for MC-Min-ATSP......Page 648
References......Page 650
1. Introduction......Page 651
2. Width parameters......Page 654
3. Algorithm for bounded adaptive width......Page 656
4. Hardness result for unbounded adaptive width......Page 657
5. Relation of bounded fractional hypertree width and bounded adaptive width......Page 659
5.1. Lower bound on fractional hypertree width......Page 660
References......Page 662
1. Introduction......Page 663
2.2. Run DAG and Acceptance......Page 665
2.3. Bu¨chi Complementation......Page 666
2.4. Tight Level Rankings......Page 667
3.1. Construction......Page 668
3.2. Correctness......Page 669
3.3. Complexity......Page 670
4.1. Construction......Page 671
4.2. Correctness......Page 672
5. Discussion......Page 673
References......Page 674
1. Introduction......Page 687
2. Preliminaries......Page 689
3. A Stronger Linear Programming Bound via Clique Constraints......Page 690
4. Formula Size of Majority Functions......Page 691
5. Formula Size of Unbalanced Recursive Ternary Majority Functions......Page 692
6. Monotone Formula Size of Balanced Recursive Ternary Majority Functions......Page 694
Acknowledgment......Page 697
References......Page 698
1. Introduction......Page 699
2.1. Notation......Page 702
2.3. Balanced Tables......Page 703
3. Increasing the randomness rate of strings......Page 705
4. Increasing the randomness rate of sequences......Page 707
References......Page 709