@incollection{Flajolet/06,
AUTHOR = {Flajolet, Philippe},
TITLE = {The ubiquitous digital tree},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {1-22},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Itkis-Levin/06,
AUTHOR = {Itkis, Gene and Levin, Leonid A.},
TITLE = {Flat holonomies on automata networks},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {23-49},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Muller-Olm-Petter-Seidl/06,
AUTHOR = {M{\"{u}}ller-Olm, Markus and Petter, Michael and Seidl, Helmut},
TITLE = {Interprocedurally analyzing polynomial identities},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {50-67},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fagerberg-Pagh-Pagh/06,
AUTHOR = {Fagerberg, Rolf and Pagh, Anna and Pagh, Rasmus},
TITLE = {External string sorting: Faster and cache-oblivious},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {68-79},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bialynicka-Birula-Grossi/06,
AUTHOR = {Bialynicka-Birula, Iwona and Grossi, Roberto},
TITLE = {Amortized rigidness in dynamic Cartesian trees},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {80-91},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Belal-Elmasry/06,
AUTHOR = {Belal, Ahmed and Elmasry, Amr},
TITLE = {Distribution-sensitive construction of minimum-redundancy prefix codes},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {92-103},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Krieger/06,
AUTHOR = {Krieger, Dalia},
TITLE = {On critical exponents in fixed points of binary $k$-uniform morphisms},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {104-114},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Agrawal-Saxena/06,
AUTHOR = {Agrawal, Manindra and Saxena, Nitin},
TITLE = {Equivalence of $F$-algebras and cubic forms},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {115-126},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Beal-Perrin/06,
AUTHOR = {B{\'{e}}al, Marie-Pierre and Perrin, Dominique},
TITLE = {Complete codes in a sofic shift},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {127-136},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fortnow-Lee-Vereshchagin/06,
AUTHOR = {Fortnow, Lance and Lee, Troy and Vereshchagin, Nikolai K.},
TITLE = {Kolmogorov complexity with error},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {137-148},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_10},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kjos-Hanssen-Merkle-Stephan/06,
AUTHOR = {Kjos-Hanssen, Bj{\o}rn and Merkle, Wolfgang and Stephan, Frank},
TITLE = {Kolmogorov complexity and the recursion theorem},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {149-161},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_11},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Wehner/06,
AUTHOR = {Wehner, Stephanie},
TITLE = {Entanglement in interactive proof systems with binary answers},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {162-171},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_12},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ambainis-Spalek/06,
AUTHOR = {Ambainis, Andris and {\v{S}}palek, Robert},
TITLE = {Quantum algorithms for matching and network flows},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {172-183},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_13},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Rytter/06,
AUTHOR = {Rytter, Wojciech},
TITLE = {The number of runs in a string: Improved analysis of the linear upper bound},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {184-195},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chakrabarti-Ba-Muthukrishnan/06,
AUTHOR = {Chakrabarti, Amit and Ba, Khanh Do and Muthukrishnan, S.},
TITLE = {Estimating entropy and entropy norm on data streams},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {196-205},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_15},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Golovin-Goyal-Ravi/06,
AUTHOR = {Golovin, Daniel and Goyal, Vineet and Ravi, R.},
TITLE = {Pay today for a rainy day: Improved approximation algorithms for demand-robust min-cut and shortest path problems},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {206-217},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_16},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Aland-Dumrauf-Gairing-Monien-Schoppmann/06,
AUTHOR = {Aland, Sebastian and Dumrauf, Dominic and Gairing, Martin and Monien, Burkhard and Schoppmann, Florian},
TITLE = {Exact price of anarchy for polynomial congestion games},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {218-229},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chakaravarthy-Roy/06,
AUTHOR = {Chakaravarthy, Venkatesan T. and Roy, Sambuddha},
TITLE = {Oblivious symmetric alternation},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {230-241},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Sayag-Fine-Mansour/06,
AUTHOR = {Sayag, Tzur and Fine, Shai and Mansour, Yishay},
TITLE = {Combining multiple heuristics},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {242-253},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_19},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Elbassioni-Mustafa/06,
AUTHOR = {Elbassioni, Khaled M. and Mustafa, Nabil H.},
TITLE = {Conflict-free colorings of rectangles ranges},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {254-263},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_20},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Damian-Flatland-ORourke/06,
AUTHOR = {Damian, Mirela and Flatland, Robin Y. and O'Rourke, Joseph},
TITLE = {Grid vertex-unfolding orthogonal polyhedra},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {264-276},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_21},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fu/06,
AUTHOR = {Fu, Bin},
TITLE = {Theory and application of width bounded geometric separator},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {277-288},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_22},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Barany/06,
AUTHOR = {B{\'{a}}r{\'{a}}ny, Vince},
TITLE = {Invariants of automatic presentations and semi-synchronous transductions},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {289-300},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_23},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Finkel/06,
AUTHOR = {Finkel, Olivier},
TITLE = {On the accepting power of 2-tape B{\"{u}}chi automata},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {301-312},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_24},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Maurer/06,
AUTHOR = {M{\"{a}}urer, Ina},
TITLE = {Weighted picture automata and weighted logics},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {313-324},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chatterjee-Majumdar-Henzinger/06,
AUTHOR = {Chatterjee, Krishnendu and Majumdar, Rupak and Henzinger, Thomas A.},
TITLE = {Markov decision processes with multiple objectives},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {325-336},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Penna-Ventre/06,
AUTHOR = {Penna, Paolo and Ventre, Carmine},
TITLE = {The algorithmic structure of group strategyproof budget-balanced cost-sharing mechanisms},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {337-348},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_27},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Christodoulou-Mirrokni-Sidiropoulos/06,
AUTHOR = {Christodoulou, George and Mirrokni, Vahab S. and Sidiropoulos, Anastasios},
TITLE = {Convergence and approximation in potential games},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {349-360},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_28},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Diaz-Thilikos/06,
AUTHOR = {D{\'{i}}az, Josep and Thilikos, Dimitrios M.},
TITLE = {Fast FPT-algorithms for cleaning grids},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {361-371},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_29},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dutta-Radhakrishnan/06,
AUTHOR = {Dutta, Chinmoy and Radhakrishnan, Jaikumar},
TITLE = {Tradeoffs in depth-two superconcentrators},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {372-383},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_30},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arvind-Kobler/06,
AUTHOR = {Arvind, Vikraman and K{\"{o}}bler, Johannes},
TITLE = {On hypergraph and graph isomorphism with bounded color classes},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {384-395},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_31},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Rumyantsev-Ushakov/06,
AUTHOR = {Rumyantsev, A.Yu. and Ushakov, M.A.},
TITLE = {Forbidden substrings, Kolmogorov complexity and almost periodic sequences},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {396-407},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_32},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hitchcock/06,
AUTHOR = {Hitchcock, John M.},
TITLE = {Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {408-419},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_33},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Barany-Loding-Serre/06,
AUTHOR = {B{\'{a}}r{\'{a}}ny, Vince and L{\"{o}}ding, Christof and Serre, Olivier},
TITLE = {Regularity problems for visibly pushdown languages},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {420-431},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schnitger/06,
AUTHOR = {Schnitger, Georg},
TITLE = {Regular expressions and NFAs without $\epsilon$-transitions},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {432-443},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_35},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Glasser-Pavan-Selman-Zhang/06,
AUTHOR = {Gla{\ss}er, Christian and Pavan, Aduri and Selman, Alan L. and Zhang, Liyu},
TITLE = {Redundancy in complete sets},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {444-454},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Buhrman-Torenvliet-Unger/06,
AUTHOR = {Buhrman, Harry and Torenvliet, Leen and Unger, Falk},
TITLE = {Sparse selfreducible sets and polynomial size circuit lower bounds},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {455-468},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_37},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fortnow-Klivans/06,
AUTHOR = {Fortnow, Lance and Klivans, Adam R.},
TITLE = {Linear advice for randomized logarithmic space},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {469-476},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Engelfriet-Hoogeboom/06,
AUTHOR = {Engelfriet, Joost and Hoogeboom, Hendrik Jan},
TITLE = {Nested pebbles and transitive closure},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {477-488},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_39},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Roy-Straubing/06,
AUTHOR = {Roy, Amitabha and Straubing, Howard},
TITLE = {Definability of languages by generalized first-order formulas over (N, +)},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {489-499},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_40},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bauland-Hemaspaandra-Schnoor-Schnoor/06,
AUTHOR = {Bauland, Michael and Hemaspaandra, Edith and Schnoor, Henning and Schnoor, Ilka},
TITLE = {Generalized modal satisfiability},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {500-511},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_41},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chatterjee-Henzinger/06,
AUTHOR = {Chatterjee, Krishnendu and Henzinger, Thomas A.},
TITLE = {Strategy improvement and randomized subexponential algorithms for stochastic parity games},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {512-523},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_42},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Berwanger-Dawar-Hunter-Kreutzer/06,
AUTHOR = {Berwanger, Dietmar and Dawar, Anuj and Hunter, Paul and Kreutzer, Stephan},
TITLE = {DAG-width and parity games},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {524-536},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_43},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Romashchenko/06,
AUTHOR = {Romashchenko, Andrei E.},
TITLE = {Reliable computations based on locally decodable codes},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {537-548},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cohen-Peleg/06,
AUTHOR = {Cohen, Reuven and Peleg, David},
TITLE = {Convergence of autonomous mobile robots with inaccurate sensors and movements},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {549-560},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_45},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Molle-Richter-Rossmanith/06,
AUTHOR = {M{\"{o}}lle, Daniel and Richter, Stefan and Rossmanith, Peter},
TITLE = {A faster algorithm for the Steiner tree problem},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {561-570},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_46},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Doerr/06,
AUTHOR = {Doerr, Benjamin},
TITLE = {Generating randomized roundings with cardinality constraints and derandomizations},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {571-583},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_47},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Khandekar-Pandit/06,
AUTHOR = {Khandekar, Rohit and Pandit, Vinayaka},
TITLE = {Online sorting buffers on line},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {584-595},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_48},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Azar-Chaiutin/06,
AUTHOR = {Azar, Yossi and Chaiutin, Yoel},
TITLE = {Optimal node routing},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {596-607},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_49},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fotakis/06,
AUTHOR = {Fotakis, Dimitris},
TITLE = {Memoryless facility location in one pass},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {608-620},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Albers-Fujiwara/06,
AUTHOR = {Albers, Susanne and Fujiwara, Hiroshi},
TITLE = {Energy-efficient algorithms for flow time minimization},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {621-633},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_51},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Etessami-Yannakakis/06,
AUTHOR = {Etessami, Kousha and Yannakakis, Mihalis},
TITLE = {Efficient qualitative analysis of classes of Recursive Markov Decision Processes and Simple Stochastic Games},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {634-645},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_52},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bodirsky-Dalmau/06,
AUTHOR = {Bodirsky, Manuel and Dalmau, V{\'{i}}ctor},
TITLE = {Datalog and constraint satisfaction with infinite templates},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {646-659},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_53},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Limaye-Mahajan-MN/06,
AUTHOR = {Limaye, Nutan and Mahajan, Meena and M.N., Jayalal Sarma},
TITLE = {Evaluating monotone circuits on cylinders, planes and tori},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {660-671},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_54},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Healy-Viola/06,
AUTHOR = {Healy, Alexander and Viola, Emanuele},
TITLE = {Constant-depth circuits for arithmetic in finite fields of characteristic two},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {672-683},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_55},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kuske/06,
AUTHOR = {Kuske, Dietrich},
TITLE = {Weighted asynchronous cellular automata},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {684-695},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_56},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Goldstein-Kobayashi/06,
AUTHOR = {Goldstein, Darin and Kobayashi, Kojiro},
TITLE = {On the complexity of the "most general" Firing Squad Synchronization Problem},
BOOKTITLE = {Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS'2006 (Marseille, France, February 23-25, 2006)},
SERIES = {LNCS},
VOLUME = {3884},
PAGES = {696-711},
YEAR = {2006},
EDITOR = {Durand, Bruno and Thomas, Wolfgang},
URL = {http://dx.doi.org/10.1007/11672142_57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}