STACS 2008 February 21-23, 2008, Bordeaux, France

25th International Symposium on Theoretical Aspects of Computer Science



Susanne Albers and Pascal Weil (Eds.)
ISBN 978-3-939897-06-4, LIPICS Vol. 1 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 11 MB)
Search Publication Server

Authors
  • Albers, Susanne
  • Albert, Pilar
  • Ambainis, Andris
  • Ballier, Alexis
  • Bárány, Vince
  • Bienvenu, Laurent
  • Björklund, Andreas
  • Bläser, Markus
  • Bodlaender, Hans L.
  • Bonifaci, Vincenzo
  • Bouyer, Patricia
  • Briest, Patrick
  • Brody, Joshua
  • Chakaravarthy, Venkatesan T.
  • Chakrabarti, Amit
  • Chen, Chao
  • Colin de Verdiére, Éric
  • Cook, Atlas F.
  • Crochemore, Maxime
  • Damian, Mirela
  • Datta, Samir
  • de Souza, Rodrigo
  • Dietzfelbinger, Martin
  • Dufourd, Jean-Francois
  • Durand, Bruno
  • Erlebach, Thomas
  • Esparza, Javier
  • Fischer , Diana
  • Flatland, Robin
  • Freedman, Daniel
  • Ganzow, Tobias
  • Gelade, Wouter
  • Glasser, Christian
  • Grädel, Erich
  • Hagerup, Torben
  • Hemaspaandra, Edith
  • Hoang, Viet Tung
  • Hoefer, Martin
  • Hoffmann, Christian
  • Hoffmann, Michael
  • Husfeldt, Thore
  • Ilie, Lucian
  • Iliopoulos, Costas S.
  • Jansen, Klaus
  • Jeandal, Emmanuel
  • Jez, Artur
  • Kaiser, Lukasz
  • Kanj, Iyad A.
  • Kao, Jui-Yi
  • Kaski, Petteri
  • Kiefer, Stefan
  • Kinne, Jeff
  • Klaedtke, Felix
  • Koivisto, Mikko
  • Kojevnikov, Arist
  • Korteweg, Peter
  • Krizanc, Danny
  • Krysta, Piotr
  • Kubica, Marcin
  • Kulkarni, Raghav
  • Kuske, Dietrich
  • Lauen, Sören
  • Lehtinen, Petri
  • Li, Angsheng
  • Lotker, Zvi
  • Lovett, Shachar
  • Lu, Pinyan
  • Luttenberger, Michael
  • Marchetti-Spaccamela, Alberto
  • Markey, Nicolas
  • Mayordomo, Elvira
  • Mestre, Julián
  • Meyer, Ulrich
  • Mihal'ák, Matús
  • Minzlaff, Moritz
  • Mishna, Marni
  • Moser, Philip
  • Muchnik, Andrej
  • Murlak, Filip
  • Neven, Frank
  • Nikolenko, Sergey I.
  • Okhotin, Alexander
  • O'Rourke, Joseph
  • Ouaknine, Joël
  • Patt-Shamir, Boaz
  • Pelsmajer, Michael J.
  • Perifel, Sylvain
  • Perkovic, Ljubomir
  • Pin, Jean-Eric
  • Rahman, M. Sohel
  • Raman, Rajeev
  • Ramaswani, Suneeta
  • Rawitz, Dror
  • Rosgen, Bill
  • Rowe, Jonathan E.
  • Roy, Sambuddha
  • Rubin, Sasha
  • Saha, Chandan
  • Sakarovitch, Jacques
  • Schaefer, Marcus
  • Schmitz, Heinz
  • Schnoebelen, Philippe
  • Schnoor, Henning
  • Schrijver, Alexander
  • Schwentick, Thomas
  • Selivanov, Victor
  • Shallit, Jeffrey
  • Shen, Alexander
  • Silva, Pedro V.
  • Stougie, Leen
  • Sung, Wing-Kin
  • Thierauf, Thomas
  • Valmari, Antti
  • van Melkebeek, Dieter
  • van Rooij, Johan M. M.
  • Veraschagin, Nikolay
  • Wagner, Fabian
  • Walen, Tomasz
  • Wegener, Ingo
  • Weil, Pascal
  • Wenk, Carola
  • Woelfel, Philipp
  • Wolff, Alexander
  • Worrell, James
  • Xia, Ge
  • Xia, Mingji
  • Xu, Zhi
  • Yannakakis, Mihalis
  • Yu, Changyuan
  • Zabrocki,Mike
  • Zelke, Mariano
    		•

    		  
    Abstracts Collection -- 25th International Symposium on Theoretical Aspects of Computer Science
    Authors: Albers, Susanne ; Weil, Pascal

    Abstract | Document (318 KB) | BibTeX

    Preface -- 25th International Symposium on Theoretical Aspects of Computer Science
    Authors: Albers, Susanne ; Weil, Pascal

    Abstract | Document (164 KB) | BibTeX

    Understanding Maximal Repetitions in Strings
    Authors: Crochemore, Maxime ; Ilie, Lucian

    Abstract | Document (145 KB) | BibTeX

    A Little Bit Infinite? On Adding Data to Finitely Labelled Structures (Abstract)
    Authors: Schwentick, Thomas

    Abstract | Document (71 KB) | BibTeX

    Equilibria, Fixed Points, and Complexity Classes
    Authors: Yannakakis, Mihalis

    Abstract | Document (208 KB) | BibTeX

    Pushdown Compression
    Authors: Albert, Pilar ; Mayordomo, Elvira ; Moser, Philip ; Perifel, Sylvain

    Abstract | Document (155 KB) | BibTeX

    Quantum search with variable times
    Authors: Ambainis, Andris

    Abstract | Document (175 KB) | BibTeX

    Structural aspects of tilings
    Authors: Ballier, Alexis ; Durand, Bruno ; Jeandal, Emmanuel

    Abstract | Document (263 KB) | BibTeX

    Limit complexities revisited
    Authors: Bienvenu, Laurent ; Muchnik, Andrej ; Shen, Alexander ; Veraschagin, Nikolay

    Abstract | Document (167 KB) | BibTeX

    Trimmed Moebius Inversion and Graphs of Bounded Degree
    Authors: Björklund, Andreas ; Husfeldt, Thore ; Kaski, Petteri ; Koivisto, Mikko

    Abstract | Document (260 KB) | BibTeX

    On the Complexity of the Interlace Polynomial
    Authors: Bläser, Markus ; Hoffmann, Christian

    Abstract | Document (210 KB) | BibTeX

    Minimizing Flow Time in the Wireless Gathering Problem
    Authors: Bonifaci, Vincenzo ; Korteweg, Peter ; Marchetti-Spaccamela, Alberto ; Stougie, Leen

    Abstract | Document (185 KB) | BibTeX

    On Termination for Faulty Channel Machines
    Authors: Bouyer, Patricia ; Markey, Nicolas ; Ouaknine, Joël ; Schnoebelen, Philippe ; Worrell, James

    Abstract | Document (177 KB) | BibTeX

    Stackelberg Network Pricing Games
    Authors: Briest, Patrick ; Hoefer, Martin ; Krysta, Piotr

    Abstract | Document (203 KB) | BibTeX

    Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound
    Authors: Brody, Joshua ; Chakrabarti, Amit

    Abstract | Document (191 KB) | BibTeX

    Finding Irrefutable Certificates for S_2^p via Arthur and Merlin
    Authors: Chakaravarthy, Venkatesan T. ; Roy, Sambuddha

    Abstract | Document (182 KB) | BibTeX

    Quantifying Homology Classes
    Authors: Chen, Chao ; Freedman, Daniel

    Abstract | Document (324 KB) | BibTeX

    Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs
    Authors: Colin de Verdiére, Éric ; Schrijver, Alexander

    Abstract | Document (195 KB) | BibTeX

    Geodesic Fréchet Distance Inside a Simple Polygon
    Authors: Wenk, Carola ; Cook, Atlas F.

    Abstract | Document (203 KB) | BibTeX

    Improved Algorithms for the Range Next Value Problem and Applications
    Authors: Iliopoulos, Costas S. ; Crochemore, Maxime ; Kubica, Marcin ; Rahman, M. Sohel ; Walen, Tomasz

    Abstract | Document (207 KB) | BibTeX

    Connecting Polygonizations via Stretches and Twangs
    Authors: Damian, Mirela ; Flatland, Robin ; O'Rourke, Joseph ; Ramaswani, Suneeta

    Abstract | Document (413 KB) | BibTeX

    Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
    Authors: Datta, Samir ; Kulkarni, Raghav ; Roy, Sambuddha

    Abstract | Document (161 KB) | BibTeX

    Tight Bounds for Blind Search on the Integers
    Authors: Dietzfelbinger, Martin ; Rowe, Jonathan E. ; Wegener, Ingo ; Woelfel, Philipp

    Abstract | Document (284 KB) | BibTeX

    Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps
    Authors: Dufourd, Jean-Francois

    Abstract | Document (185 KB) | BibTeX

    Trimming of Graphs, with Application to Point Labeling
    Authors: Erlebach, Thomas ; Hagerup, Torben ; Jansen, Klaus ; Minzlaff, Moritz ; Wolff, Alexander

    Abstract | Document (187 KB) | BibTeX

    Computing Minimum Spanning Trees with Uncertainty
    Authors: Hoffmann, Michael ; Erlebach, Thomas ; Krizanc, Danny ; Mihal'ák, Matús ; Raman, Rajeev

    Abstract | Document (171 KB) | BibTeX

    Convergence Thresholds of Newton's Method for Monotone Polynomial Equations
    Authors: Esparza, Javier ; Kiefer, Stefan ; Luttenberger, Michael

    Abstract | Document (201 KB) | BibTeX

    Model Checking Games for the Quantitative µ-Calculus
    Authors: Fischer , Diana ; Grädel, Erich ; Kaiser, Lukasz

    Abstract | Document (189 KB) | BibTeX

    Order-Invariant MSO is Stronger than Counting MSO in the Finite
    Authors: Ganzow, Tobias ; Rubin, Sasha

    Abstract | Document (182 KB) | BibTeX

    Succinctness of the Complement and Intersection of Regular Expressions
    Authors: Gelade, Wouter ; Neven, Frank

    Abstract | Document (182 KB) | BibTeX

    Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages
    Authors: Glasser, Christian ; Schmitz, Heinz ; Selivanov, Victor

    Abstract | Document (199 KB) | BibTeX

    On the Complexity of Elementary Modal Logics
    Authors: Hemaspaandra, Edith ; Schnoor, Henning

    Abstract | Document (267 KB) | BibTeX

    Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees
    Authors: Hoang, Viet Tung ; Sung, Wing-Kin

    Abstract | Document (198 KB) | BibTeX

    Complexity of solutions of equations over sets of natural numbers
    Authors: Okhotin, Alexander ; Jez, Artur

    Abstract | Document (179 KB) | BibTeX

    Cardinality and counting quantifiers on omega-automatic structures
    Authors: Kaiser, Lukasz ; Rubin, Sasha ; Bárány, Vince

    Abstract | Document (187 KB) | BibTeX

    On the Induced Matching Problem
    Authors: Kanj, Iyad A. ; Pelsmajer, Michael J. ; Xia, Ge ; Schaefer, Marcus

    Abstract | Document (180 KB) | BibTeX

    On Geometric Spanners of Euclidean and Unit Disk Graphs
    Authors: Perkovic, Ljubomir ; Kanj, Iyad A.

    Abstract | Document (187 KB) | BibTeX

    The Frobenius Problem in a Free Monoid
    Authors: Kao, Jui-Yi ; Shallit, Jeffrey ; Xu, Zhi

    Abstract | Document (188 KB) | BibTeX

    Space Hierarchy Results for Randomized Models
    Authors: Kinne, Jeff ; van Melkebeek, Dieter

    Abstract | Document (161 KB) | BibTeX

    Ehrenfeucht-Fraissé Goes Automatic for Real Addition
    Authors: Klaedtke, Felix

    Abstract | Document (191 KB) | BibTeX

    New Combinatorial Complete One-Way Functions
    Authors: Kojevnikov, Arist ; Nikolenko, Sergey I.

    Abstract | Document (152 KB) | BibTeX

    Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic
    Authors: Kuske, Dietrich

    Abstract | Document (183 KB) | BibTeX

    Geometric Set Cover and Hitting Sets for Polytopes in R³
    Authors: Lauen, Sören

    Abstract | Document (176 KB) | BibTeX

    A Theory for Valiant's Matchcircuits (Extended Abstract)
    Authors: Li, Angsheng ; Xia, Mingji

    Abstract | Document (228 KB) | BibTeX

    Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental
    Authors: Lotker, Zvi ; Patt-Shamir, Boaz ; Rawitz, Dror

    Abstract | Document (202 KB) | BibTeX

    Lower bounds for adaptive linearity tests
    Authors: Lovett, Shachar

    Abstract | Document (166 KB) | BibTeX

    Lagrangian Relaxation and Partial Cover (Extended Abstract)
    Authors: Mestre, Julián

    Abstract | Document (226 KB) | BibTeX

    An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines
    Authors: Lu, Pinyan ; Yu, Changyuan

    Abstract | Document (173 KB) | BibTeX

    On Dynamic Breadth-First Search in External-Memory
    Authors: Meyer, Ulrich

    Abstract | Document (227 KB) | BibTeX

    Analytic aspects of the shuffle product
    Authors: Mishna, Marni ; Zabrocki,Mike

    Abstract | Document (175 KB) | BibTeX

    Weak index versus Borel rank
    Authors: Murlak, Filip

    Abstract | Document (171 KB) | BibTeX

    A Mahler's theorem for functions from words to integers
    Authors: Pin, Jean-Eric ; Silva, Pedro V.

    Abstract | Document (180 KB) | BibTeX

    Distinguishing Short Quantum Computations
    Authors: Rosgen, Bill

    Abstract | Document (172 KB) | BibTeX

    Factoring Polynomials over Finite Fields using Balance Test
    Authors: Saha, Chandan

    Abstract | Document (176 KB) | BibTeX

    On the decomposition of k-valued rational relations
    Authors: Sakarovitch, Jacques ; de Souza, Rodrigo

    Abstract | Document (208 KB) | BibTeX

    The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
    Authors: Thierauf, Thomas ; Wagner, Fabian

    Abstract | Document (168 KB) | BibTeX

    Efficient Minimization of DFAs with Partial Transition
    Authors: Valmari, Antti ; Lehtinen, Petri

    Abstract | Document (172 KB) | BibTeX

    Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set
    Authors: van Rooij, Johan M. M. ; Bodlaender, Hans L.

    Abstract | Document (168 KB) | BibTeX

    Weighted Matching in the Semi-Streaming Model
    Authors: Zelke, Mariano

    Abstract | Document (176 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI