default search action
18th STACS 2001: Dresden, Germany
- Afonso Ferreira, Horst Reichel:
STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings. Lecture Notes in Computer Science 2010, Springer 2001, ISBN 3-540-41695-1
Invited Presentations
- Julien Cassaigne:
Recurrence in Infinite Words. 1-11 - Martin Grohe:
Generalized Model-Checking Problems for First-Order Logic. 12-26 - Dexter Kozen:
Myhill-Nerode Relations on Automatic Systems and the Completeness of Kleene Algebra. 27-38
Contributions
- Luca Aceto, Wan J. Fokkink, Anna Ingólfsdóttir:
2-Nested Simulation Is Not Finitely Equationally Axiomatizable. 39-50 - Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe:
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. 51-62 - Helmut Alt, Christian Knauer, Carola Wenk:
Matching Polygonal Curves with Respect to the Fréchet Distance. 63-74 - Andris Ambainis, Arnolds Kikusts, Maris Valdats:
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. 75-86 - Martin Beaudry, François Lemieux, Denis Thérien:
Star-Free Open Languages and Aperiodic Loops. 87-98 - Markus Bläser:
A (5/2)n2-Lower Bound for the Multiplicative Complexity of n×n-Matrix Multiplication. 99-109 - Amit Chakrabarti, Subhash Khot, Yaoyun Shi:
Evasiveness of Subgraph Containment and Related Properties. 110-120 - Andrea E. F. Clementi, Pierluigi Crescenzi
, Paolo Penna, Gianluca Rossi, Paola Vocca
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. 121-131 - Zhe Dang, Pierluigi San Pietro, Richard A. Kemmerer:
On Presburger Liveness of Discrete Timed Automata. 132-143 - François Denis, Aurélien Lemay, Alain Terlutte:
Residual Finite State Automata. 144-157 - Anders Dessmark, Andrzej Pelc:
Deterministic Radio Broadcasting at Low Cost. 158-169 - Volker Diekert, Claudio Gutierrez
The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete. 170-182 - Benjamin Doerr, Anand Srivastav:
Recursive Randomized Coloring Beats Fair Dice Random Colorings. 183-194 - Rodney G. Downey, Denis R. Hirschfeldt, André Nies:
Randomness, Computability, and Density. 195-205 - Pavol Duris, Juraj Hromkovic, Stasys Jukna
On Multipartition Communication Complexity. 206-217 - Robert Elsässer, Rastislav Kralovic
Scalable Sparse Topologies with Small Spectrum. 218-229 - Leah Epstein
Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios. 230-237 - Cristina G. Fernandes
The UPS Problem. 238-246 - Paola Flocchini, Giuseppe Prencipe
Gathering of Asynchronous Oblivious Robots with Limited Visibility. 247-258 - Anahí Gajardo
Generalized Langton's Ant: Dynamical Behavior and Complexity. 259-270 - Clemente Galdi, Christos Kaklamanis, Manuela Montangero, Pino Persiano:
Optimal and Approximate Station Placement in Networks (With Applications to Multicasting and Space Efficient Traversals). 271-282 - Ricard Gavaldà
Learning Expressions over Monoids. 283-293 - Andreas Goerdt, Michael Krivelevich:
Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods. 294-304 - Massimiliano Goldwurm, Beatrice Palano, Massimo Santini:
On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages. 305-316 - Torben Hagerup, Torsten Tholey:
Efficient Minimal Perfect Hashing in Nearly Minimal Space. 317-326 - Prahladh Harsha
Small PCPs with Low Query Complexity. 327-338 - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Space Efficient Algorithms for Series-Parallel Graphs. 339-352 - David Janin, Jerzy Marcinkowski:
A Toolkit for First Order Extensions of Monadic Games. 353-364 - Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel:
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. 365-375 - Matthias Jantzen, Alexy Kurganskyy:
Refining the Hierarchy of Blind Multicounter Languages. 376-387 - Juhani Karhumäki, Leonid P. Lisovik:
A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab*c. 388-395 - Jarkko Kari, Cristopher Moore
New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata. 396-406 - Lefteris M. Kirousis, Phokion G. Kolaitis:
The Complexity of Minimal Satisfiability Problems. 407-418 - Matthias Krause, Stefan Lucks:
On the Minimal Hardware Complexity of Pseudorandom Function Generators. 419-430 - Piotr Krysta, V. S. Anil Kumar:
Approximation Algorithms for Minimum Size 2-Connectivity Problems. 431-442 - Dietrich Kuske:
A Model Theoretic Proof of Büchi-Type Theorems and First-Order Logic for N-Free Pomsets. 443-454 - Clemens Lautemann, Nicole Schweikardt:
An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases. 455-466 - Giacomo Lenzi:
A New Logical Characterization of Büchi Automata. 467-477 - Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki:
A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph. 478-489 - Markus Müller-Olm:
The Complexity of Copy Constant Detection in Parallel Programs. 490-501 - Giri Narasimhan
Approximation Algorithms for the Bottleneck Stretch Factor Problem. 502-513 - Dirk Pattinson:
Semantical Principles in the Modal Logic of Coalgebras. 514-526 - Klaus Reinhardt:
The #a = #b Pictures Are Recognizable. 527-538 - Victor L. Selivanov:
A Logical Approach to Decidability of Hierarchies of Regular Star-Free Languages. 539-550 - Howard Straubing, Denis Thérien:
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. 551-562 - Philipp Woelfel:
New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing. 563-574
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-14 22:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: