×

zbMATH — the first resource for mathematics

STACS 2008. 25th international symposium on theoretical aspects of computer science, Bordeaux, France, February 21–23, 2008. (English) Zbl 1213.68020
LIPIcs – Leibniz International Proceedings in Informatics 1. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-06-4). 680 p., electronic. (2008).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 1115.68007; Zbl 1198.68063].
Indexed articles:
Crochemore, Maxime; Ilie, Lucian, Understanding maximal repetitions in strings, 11-16, electronic only [Zbl 1259.68249]
Schwentick, Thomas, A little bit infinite? On adding data to finitely labelled structures, 17-18, electronic only [Zbl 1259.68041]
Yannakakis, Mihalis, Equilibria, fixed points, and complexity classes, 19-38, electronic only [Zbl 1259.68075]
Albert, Pilar; Mayordomo, Elvira; Moser, Philip; Perifel, Sylvain, Pushdown compression, 39-48, electronic only [Zbl 1259.68045]
Ambainis, Andris, Quantum search with variable times, 49-61, electronic only [Zbl 1259.68069]
Ballier, Alexis; Durand, Bruno; Jeandal, Emmanuel, Structural aspects of tilings, 61-72, electronic only [Zbl 1258.05023]
Bienvenu, Laurent; Muchnik, Andrej; Shen, Alexander; Verashchagin, Nikolay, Limit complexities revisited, 73-84, electronic only [Zbl 1259.68099]
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko, Trimmed Moebius inversion and graphs of bounded degree, 85-96, electronic only [Zbl 1259.68154]
Bläser, Markus; Hoffmann, Christian, On the complexity of the interlace polynomial, 97-108, electronic only [Zbl 1259.68076]
Bonifaci, Vincenzo; Korteweg, Peter; Marchetti-Spaccamela, Alberto; Stoogie, Leen, Minimizing flow time in the wireless gathering problem, 109-120, electronic only [Zbl 1259.68012]
Bouyer, Patricia; Markey, Nicolas; Ouaknine, Joël; Schnoebelen, Philippe; Worrell, James, On termination for faulty channel machines, 121-132, electronic only [Zbl 1259.68120]
Briest, Patrick; Hoefer, Martin; Krysta, Piotr, Stackelberg network pricing games, 133-142, electronic only [Zbl 1259.68234]
Brody, Joshua; Chakrabarti, Amit, Sublinear communication protocols for multi-party pointer jumping and a related lower bound, 145-165, electronic only [Zbl 1259.68056]
Chakaravarthy, Venkatesan T.; Roy, Sambuddha, Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin, 157-168, electronic only [Zbl 1259.68071]
Chen, Chao; Freedman, Daniel, Quantifying homology classes, 169-180, electronic only [Zbl 1259.68088]
De Verdière, Éric Colin; Schrijver, Alexander, Shortest vertex-disjoint two-face paths in planar graphs, 181-192, electronic only [Zbl 1259.68089]
Wenk, Carola; Cook, Atlas F. IV, Geodesic Fréchet distance inside a simple polygon, 193-204, electronic only [Zbl 1259.68214]
Iliopoulos, Costas S.; Crochemore, Maxime; Kubica, Marcin; Rahman, M. Sohel; Waleń, Tomasz, Improved algorithms for the range next value problem and applications, 205-216, electronic only [Zbl 1259.68226]
Damian, Mirela; Flatland, Robin; O’Rourke, Joseph; Ramaswani, Suneeta, Connecting polygonizations via stretches and twangs, 217-228, electronic only [Zbl 1259.68224]
Datta, Samir; Kulkarni, Raghav; Roy, Sambuddha, Deterministically isolating a perfect matching in bipartite planar graphs, 229-240, electronic only [Zbl 1259.68158]
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp, Tight bounds for blind search on the integers, 241-252, electronic only [Zbl 1259.68151]
Dufourd, Jean-François, Discrete Jordan curve theorem: a proof formalized in Coq with hypermaps, 253-264, electronic only [Zbl 1259.68179]
Erlebach, Thomas; Hagerup, Torben; Jansen, Klaus; Minzlaff, Moritz; Wolff, Alexander, Trimming of graphs, with application to point labeling, 265-276, electronic only [Zbl 1258.05043]
Hoffmann, Michael; Erlebach, Thomas; Krizanc, Danny; Mihal’ák, Matúš; Raman, Rajeev, Computing minimum spanning trees with uncertainty, 277-288, electronic only [Zbl 1259.68161]
Esparza, Javier; Kiefer, Stefan; Luttenberger, Michael, Convergence thresholds of Newton’s method for monotone polynomial equations, 289-300, electronic only [Zbl 1259.65225]
Fischer, Diana; Grädel, Erich; Kaiser, Lukasz, Model checking games for the quantitative \(\mu\)-calculus, 301-312, electronic only [Zbl 1259.68124]
Ganzow, Tobias; Rubin, Sasha, Order-invariant MSO is stronger than counting MSO in the finite, 313-324, electronic only [Zbl 1259.03018]
Gelade, Wouter; Neven, Frank, Succinctness of the complement and intersection of regular expressions, 325-336, electronic only [Zbl 1259.68107]
Glasser, Christian; Schmitz, Heinz; Selivanov, Victor, Efficient algorithms for membership in Boolean hierarchies of regular languages, 337-348, electronic only [Zbl 1259.68108]
Hemaspaandra, Edith; Schnoor, Henning, On the complexity of elementary modal logics, 349-360, electronic only [Zbl 1259.68072]
Hoang, Viet Tung; Sung, Wing-Kin, Fixed parameter polynomial time algorithms for maximum agreement and compatible supertrees, 361-372, electronic only [Zbl 1259.68258]
Okhotin, Alexander; Jeż, Artur, Complexity of solutions of equations over sets of natural numbers, 373-384, electronic only [Zbl 1259.68083]
Kaiser, Lukasz; Rubin, Sasha; Bárány, Vince, Cardinality and counting quantifiers on omega-automatic structures, 385-396, electronic only [Zbl 1259.68109]
Kanj, Iyad A.; Pelsmajer, Michael J.; Xia, Ge; Schaefer, Marcus, On the induced matching problem, 397-408, electronic only [Zbl 1259.68095]
Perković, Ljubomir; Kanj, Iyad A., On geometric spanners of Euclidean and unit disk graphs, 409-420, electronic only [Zbl 1259.68163]
Kao, Jui-Yi; Shallit, Jeffrey; Xu, Zhi, The Frobenius problem in a free monoid, 421-432, electronic only [Zbl 1259.68166]
Kinne, Jeff; Van Melkebeek, Dieter, Space hierarchy results for randomized models, 433-444, electronic only [Zbl 1259.68061]
Klaedtke, Felix, Ehrenfeucht-Fraïssé goes automatic for real addition, 445-456, electronic only [Zbl 1259.68110]
Kojevnikov, Arist; Nikolenko, Sergey I., New combinatorial complete one-way functions, 457-466, electronic only [Zbl 1259.68080]
Kuske, Dietrich, Compatibility of Shelah and Stupp’s and Muchnik’s iteration with fragments of monadic second order logic, 467-478, electronic only [Zbl 1259.03019]
Lauen, Sören, Geometric set cover and hitting sets for polytopes in \({\mathbb R}^3\), 479-490, electronic only [Zbl 1259.68210]
Li, Angsheng; Xia, Mingji, A theory for Valiant’s matchcircuits (Extended abstract), 491-205, electronic only [Zbl 1259.68062]
Lotker, Zvi; Patt-Shamir, Boaz; Rawitz, Dror, Rent, lease or buy: randomized algorithms for multislope ski rental, 503-514, electronic only [Zbl 1259.68231]
Lovett, Shachar, Lower bounds for adaptive linearity tests, 515-526, electronic only [Zbl 1259.68232]
Lu, Pinyan; Yu, Changyuan, An improved randomized truthful mechanism for scheduling unrelated machines, 527-538, electronic only [Zbl 1259.68022]
Meyer, Ulrich, On dynamic breadth-first search in external-memory, 551-560, electronic only [Zbl 1259.68162]
Mishna, Marni; Zabrocki, Mike, Analytic aspects of the shuffle product, 561-572, electronic only [Zbl 1259.68111]
Murlak, Filip, Weak index versus Borel rank, 573-584, electronic only [Zbl 1259.68112]
Pin, Jean-Éric; Silva, Pedro V., A Mahler’s theorem for functions from words to integers, 585-596, electronic only [Zbl 1259.68138]
Rosgen, Bill, Distinguishing short quantum computations, 597-608, electronic only [Zbl 1259.68070]
Saha, Chandan, Factoring polynomials over finite fields using balance test, 609-620, electronic only [Zbl 1259.68245]
Sakarovitch, Jacques; De Souza, Rodrigo, On the decomposition of \(k\)-valued rational relations, 621-632, electronic only [Zbl 1259.68113]
Thierauf, Thomas; Wagner, Fabian, The isomorphism problem for planar 3-connected graphs is in unambiguous logspace, 633-644, electronic only [Zbl 1259.68164]
Valmari, Antti; Lehtinen, Petri, Efficient minimization of DFAs with partial transition, 645-656, electronic only [Zbl 1259.68115]
Van Rooij, Johan M. M.; Bodlaender, Hans L., Design by measure and conquer. A faster exact algorithm for dominating set, 657-668, electronic only [Zbl 1259.68097]
Zelke, Mariano, Weighted matching in the semi-streaming model, 669-680, electronic only [Zbl 1259.68240]
Mestre, Julián, Lagrangian relaxation and partial cover (Extended abstract), 12 p., electronic only [Zbl 1259.68239]

MSC:
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
00B25 Proceedings of conferences of miscellaneous specific interest
Software:
Coq
PDF BibTeX XML Cite
Full Text: Link Link