STACS 93. 10th annual symposium on theoretical aspects of computer science, Würzburg, Germany, February 25–27, 1993. Proceedings. (English) Zbl 0866.00060

Lecture Notes in Computer Science. 665. Berlin: Springer-Verlag. XIV, 724 p. DM 134.00 /sc (1993).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 0904.68001].
Indexed articles:
Wagner, Klaus W., The alternation hierarchy for sublogarithmic space: An exciting race to STACS’93, 2-4 [Zbl 0797.68062]
von Braunmühl, Burchard, Alternation for two-way machines with sublogarithmic space, 5-15 [Zbl 0797.68056]
Liśkiewicz, Maciej; Reischuk, Rüdiger, Separating the lower levels of the sublogarithmic space hierarchy, 16-27 [Zbl 0799.68092]
Köbler, Johannes, Locating P/poly optimally in the extended low hierarchy, 28-37 [Zbl 0793.68065]
Lutz, Jack H.; Mayordomo, Elvira, Measure, stochasticity, and the density of hard languages, 38-47 [Zbl 0791.68064]
Devienne, Philippe; Lebègue, Patrick; Routier, Jean-Christophe, Halting problem of one binary Horn clause is undecidable, 48-57 [Zbl 0797.68057]
Zhou, Chaochen; Hansen, Michael R.; Sestoft, Peter, Decidability and undecidability results for duration calculus, 58-68 [Zbl 0811.68115]
Eiter, Thomas; Gottlob, Georg, The complexity of logic-based abduction, 70-79 [Zbl 0799.68089]
Kloks, T.; Kratsch, D., Treewidth of chordal bipartite graphs, 80-89 [Zbl 0799.68113]
Huckenbeck, Ulrich, On paths in networks with valves, 90-99 [Zbl 0799.68147]
Sunder, S.; He, Xin, Scheduling interval ordered tasks in parallel, 100-109 [Zbl 0799.68034]
Pietracaprina, A.; Preparata, F. P., An \(O ({\sqrt n})\)-worst-case-time solution to the granularity problem, 110-119 [Zbl 0795.68090]
Desel, Jörg; Reisig, Wolfgang, The synthesis problem of Petri nets, 120-129 [Zbl 0799.68142]
Best, Eike; Devillers, Raymond; Esparza, Javier, General refinement and recursion operators for the Petri Box calculus, 130-140 [Zbl 0791.68122]
Bonacina, Maria Paola; Hsiang, Jieh, On fairness in distributed automated deduction, 141-152 [Zbl 0792.68160]
Mayr, Ernst W.; Werchner, Ralph, Divide-and-conquer algorithms on the hypercube, 153-162 [Zbl 0799.68109]
Allender, Eric; Balcázar, Jose; Immerman, Neil, A first-order isomorphism theorem, 163-174 [Zbl 0799.68088]
Buhrman, Harry; Hoene, Albrecht; Torenvliet, Leen, Splittings, robustness and structure of complete sets, 175-184 [Zbl 0791.68061]
Hemachandra, Lane A.; Jha, Sudhir K., Defying upward and downward separation, 185-195 [Zbl 0802.68050]
Hoene, Albrecht; Nickelsen, Arfst, Counting, selecting, and sorting by query-bounded machines, 196-205 [Zbl 0791.68063]
Jantzen, M.; Petersen, H., Cancellation in context-free languages: Enrichment by reduction, 206-215 [Zbl 0799.68126]
Cassaigne, Julien, Counting overlap-free binary words, 216-225 [Zbl 0799.68153]
Narbel, Philippe, The limit set of recognizable substitution systems, 226-236 [Zbl 0799.68125]
Krob, D.; Lalonde, P., Partially commutative Lyndon words, 237-246 [Zbl 0801.68144]
Monien, B.; Feldmann, R.; Klasing, R.; Lüling, R., Parallel architectures: Design and efficient use, 247-269 [Zbl 0799.68023]
Formann, Michael, Weighted closest pairs, 270-281 [Zbl 0799.68189]
Schuierer, Sven, Rectilinear path queries in a simple rectilinear polygon, 282-293 [Zbl 0791.68165]
Czumaj, Artur, Parallel algorithm for the matrix chain product and the optimal triangulation problems. (Extended abstract), 294-305 [Zbl 0799.68184]
Dessmark, Anders; Lingas, Andrzej; Maheshwari, Anil, Multi-list ranking: Complexity and applications, 306-316 [Zbl 0799.68188]
Kučera, L.; Mehlhorn, K.; Preis, B.; Schwarzenecker, E., Exact algorithms for a geometric packing problem. (Extended abstract), 317-322 [Zbl 0799.68193]
Maler, Oded, A decomposition theorem for probabilistic transition systems, 323-332 [Zbl 0797.68117]
Montalbano, Rosa, Local automata and completion, 333-342 [Zbl 0799.68137]
Culik, Karel II; Dube, Simant, Efficient compression of wavelet coefficients for smooth and fractal-like data, 343-353 [Zbl 0795.68203]
Ibarra, Oscar H.; Jiang, Tao; Tran, Nicholas; Wang, Hui, On the equivalence of two-way pushdown automata and counter machines over bounded languages, 354-364 [Zbl 0799.68076]
Cosnard, Michel; Garzon, Max; Koiran, Pascal, Computability properties of low-dimensional dynamical systems, 365-373 [Zbl 0791.68056]
Abrahamson, Karl A.; Downey, Rodney G.; Fellows, Michael R., Fixed-parameter intractability. II. (Extended abstract), 374-385 [Zbl 0799.68086]
Fich, Faith E.; Impagliazzo, Russell; Kapron, Bruce; King, Valerie; Kutylowski, Miroslaw, Limits on the power of parallel random access machines with weak forms of write conflict resolution, 386-397 [Zbl 0842.68033]
Fenner, Stephen; Homer, Steve; Ogiwara, Mitsunori; Selman, Alan L., On using oracles that compute values, 398-407 [Zbl 0799.68090]
Gengler, Romain, Multicounter automata with sublogarithmic reversal bounds, 408-417 [Zbl 0799.68075]
Uselton, Andrew C., Structured operational semantics for concurrency and hierarchy, 418-427 [Zbl 0925.68306]
Hungar, Hardi, The complexity of verifying functional programs, 428-439 [Zbl 0799.68135]
Lentfert, P. J. A.; Swierstra, S. D., Towards the formal design of self-stabilizing distributed algorithms, 440-451 [Zbl 0791.68074]
Penczek, Wojciech, Axiomatizations of temporal logics on trace systems, 452-462 [Zbl 0791.68075]
Lürwer-Brüggemeier, Katharina; Meyer auf der Heide, Friedhelm, Capabilities and complexity of computations with integer division, 463-472 [Zbl 0791.68078]
Niedermeier, Rolf; Rossmanith, Peter, Extended locally definable acceptance types, 473-483 [Zbl 0791.68065]
Fenner, Stephen; Fortnow, Lance; Li, Lide, Gap-definability as a closure property, 484-493 [Zbl 0822.68031]
Choffrut, C.; Guerra, L., On the logical definability of some rational trace languages, 494-504 [Zbl 0791.68093]
Gilleron, Rémi; Tison, Sophie; Tommasi, Marc, Solving systems of set constraints using tree automata, 505-514 [Zbl 0797.68115]
Lugiez, D.; Moysset, J. L., Complement problems and tree automata in AC-like theories, 515-524 [Zbl 0795.68139]
Babai, László, Transparent (holographic) proofs, 525-534 [Zbl 0790.68043]
Zhang, Zhi-Li; Barrington, David A. Mix; Tarui, Jun, Computing symmetric functions with AND/OR circuits and a single MAJORITY gate, 535-544 [Zbl 0796.94020]
Maciel, Alexis; Thérien, Denis, Threshold circuits for iterated multiplication: Using AC\(^ 0\) for free, 545-554 [Zbl 0798.68077]
Beaudry, Martin; McKenzie, Pierre; Péladeau, Pierre, Circuits with monoidal gates. (Extended abstract), 555-565 [Zbl 0796.94017]
Istrail, Sorin; Zivkovic, Dejan, A non-probabilistic switching lemma for the Sipser function, 566-575 [Zbl 0796.94019]
Gergov, Jordan; Meinel, Christoph, Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs. (Extended abstract), 576-585 [Zbl 0798.68078]
Maler, Oded; Staiger, Ludwig, On syntactic congruences for \(\omega\)-languages, 586-594 [Zbl 0797.68093]
Varricchio, Stefano, A polynomial time algorithm for the equivalence of two morphisms on \(\omega\)-regular languages, 595-606 [Zbl 0797.68082]
Wilke, Thomas, Locally threshold testable languages of infinite words, 607-616 [Zbl 0799.68127]
Diekert, Volker; Muscholl, Anca, Deterministic asynchronous automata for infinite traces. (Extended abstract), 617-628 [Zbl 0799.68140]
Staiger, Ludwig, Recursive automata on infinite words, 629-639 [Zbl 0799.68139]
Sairam, S.; Vitter, Jeffrey Scott; Tamassia, Roberto, A complexity theoretic approach to incremental computation, 640-649 [Zbl 0791.68066]
Reischuk, Rüdiger; Schindelhauer, Christian, Precise average case complexity, 650-661 [Zbl 0799.68093]
Miltersen, Peter Bro, The bit probe complexity measure revisited, 662-671 [Zbl 0799.68048]
Baliga, Ganesh; Case, John; Jain, Sanjay, Language learning with some negative information, 672-681 [Zbl 0845.68066]
Lange, Steffen; Zeugmann, Thomas, Language learning with a bounded number of mind changes, 682-691 [Zbl 0797.68134]
Blundo, Carlo; De Santis, Alfredo; Vaccaro, Ugo, Efficient sharing of many secrets, 692-703 [Zbl 0796.94007]
Drexler, Rainer; Reif, Wolfgang; Schellhorn, Gerhard; Stenzel, Kurt; Stephan, Werner; Wolpers, Andreas, The KIV system – A tool for formal program development, 704-705 [Zbl 0850.68114]
Höfting, Franz; Wanke, Egon; Balmoŝan, Aurel; Bergmann, Curd, 1st Grade – A system for implementation, testing and animation of graph algorithms, 706-707 [Zbl 0789.68142]
Näher, Stefan, LEDA – A library of efficient data types and algorithms, 710-711 [Zbl 0850.68170]
de Groote, Philippe, Defining \(\lambda\)-typed \(\lambda\)-calculi by axiomatizing the typing relation, 712-723 [Zbl 0797.68144]


00B25 Proceedings of conferences of miscellaneous specific interest
68Qxx Theory of computing
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
Full Text: DOI