Automata, languages and programming. 19th international colloquium, Wien, Austria, July 13–17, 1992. Proceedings. (English) Zbl 1369.68031

Lecture Notes in Computer Science 623. Berlin: Springer-Verlag (ISBN 978-3-540-55719-7/pbk; 978-3-540-47278-0/ebook). xii, 719 p. (1992).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding colloquium see [Zbl 0753.00027].
Indexed articles:
Li, Ming; Vitányi, Paul M. B., Philosophical issues in Kolmogorov complexity, 1-15 [Zbl 1425.68149]
Straubing, Howard, Circuit complexity and the expressive power of generalized first-order formulas, 16-27 [Zbl 1425.03016]
De Santis, Alfredo; Persiano, Giuseppe; Yung, Moti, One-message statistical zero-knowledge proofs and space-bounded verifier, 28-40 [Zbl 1425.68109]
Keränen, Veikko, Abelian squares are avoidable on 4 letters, 41-52 [Zbl 1425.68331]
Karhumaäki, Juhani; Plandowski, Wojciech; Rytter, Wojciech, Polynomial size test sets for context-free languages, 53-64 [Zbl 1425.68211]
Nishida, Taishin Y., Quasi-deterministic 0L systems, 65-76 [Zbl 1425.68223]
Buntrock, Gerhard; Loryś, Krzysztof, On growing context-sensitive languages, 77-88 [Zbl 1425.68186]
Shallit, Jeffrey, Numeration systems, linear recurrences, and regular sets (extended abstract), 89-100 [Zbl 1425.11015]
Krob, Daniel, The equality problem for rational series with multiplicities in the tropical semiring is undecidable, 101-112 [Zbl 1425.68213]
Clerbout, M.; Latteux, M.; Roos, Y.; Zielonka, W., Semi-commutations and rational expressions, 113-125 [Zbl 1425.68189]
Ibarra, Oscar H.; Trân, Nicholas Q., New results concerning synchronized finite automata, 126-137 [Zbl 1425.68208]
Engelfriet, Joost, A Greibach normal form for context-free graph grammars, 138-149 [Zbl 1425.68162]
Péladeau, Pierre; Podelski, Andreas, On reverse and general definite tree languages (extended abstract), 150-161 [Zbl 1425.68225]
Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T., Reductions to sets of low information content (extended abstract), 162-173 [Zbl 1425.68125]
Sheu, Ming-Jye; Long, Timothy J., \(\mathrm{UP}\) and the low and high hierarchies: a relativized separation, 174-185 [Zbl 1425.68129]
Flajolet, Philippe, Analytic analysis of algorithms, 186-210 [Zbl 1425.68473]
Kirschenhofer, Peter; Prodinger, Helmut; Szpankowski, Wojciech, How to count quickly and accurately: a unified analysis of probabilistic counting and other related problems, 211-222 [Zbl 1425.68474]
Schmid, Ulrich, The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects, 223-234 [Zbl 1425.68024]
Dietzfelbinger, M.; Gil, J.; Matias, Y.; Pippenger, N., Polynomial hash functions are reliable (extended abstract), 235-246 [Zbl 1425.68098]
Sekar, R. C.; Ramesh, R.; Ramakrishnan, I. V., Adaptive pattern matching, 247-260 [Zbl 1425.68231]
Mansour, Yishay, Randomized interpolation and approximation of sparse polynomials (preliminary version), 261-272 [Zbl 1427.65013]
Bodlaender, Hans L.; Fellows, Mike R.; Warnow, Tandy J., Two strikes against perfect phylogeny, 273-283 [Zbl 1425.68136]
Zhang, Guo-Qiang, Disjunctive systems and \(\mathrm{L}\)-domains, 284-295 [Zbl 1425.68244]
Apostolico, Alberto; Breslauer, Dany; Galil, Zvi, Optimal parallel algorithms for periods, palindromes and squares (extended abstract), 296-307 [Zbl 1425.68466]
Broder, Andrei Z.; Frieze, Alan M.; Shamir, E.; Upfal, E., Near-perfect token distribution, 308-317 [Zbl 1425.68305]
Hagerup, Torben; Kutyłowski, Mirosław, Fast integer merging on the EREW PRAM, 318-329 [Zbl 1425.68449]
Khuller, Samir; Thurimella, Ramakrishna, Approximation algorithms for graph augmentation, 330-341 [Zbl 1425.68315]
Westbrook, Jeffery, Fast incremental planarity testing, 342-353 [Zbl 1427.68255]
La Poutré, J. A., Maintenance of triconnected components of graphs (extended abstract), 354-365 [Zbl 1427.68247]
Vazirani, Vijay V.; Yannakakis, Mihalis, Suboptimal cuts: their enumeration, weight and number (extended abstract), 366-377 [Zbl 1427.68254]
Buchberger, Bruno, Gröbner bases: an introduction, 378-379 [Zbl 1427.13035]
Bündgen, Reinhard, Buchberger’s algorithm: the term rewriter’s point of view (extended abstract), 380-391 [Zbl 1427.68373]
Comon, Hubert, Completion of rewrite systems with membership constraints, 392-403 [Zbl 1427.68134]
Rote, Günter, A new metric between polygons, and how to compute it (extended abstract), 404-415 [Zbl 1427.68337]
Paterson, Michael S.; Yao, F. Frances, On nearest-neighbor graphs, 416-426 [Zbl 1425.68439]
Matoušek, Jiří; Seidel, Raimund, A tail estimate for Mulmuley’s segment intersection algorithm, 427-438 [Zbl 1425.68436]
Chazelle, Bernard; Rosenberg, Burton, Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract), 439-449 [Zbl 1425.68430]
Kolaitis, Phokion G.; Vardi, Moshe Y., Infinitary logic for computer science, 450-473 [Zbl 1427.03049]
Chang, Edward; Manna, Zohar; Pnueli, Amir, Characterization of temporal property classes, 474-486 [Zbl 1425.68252]
Ong, C.-H. Luke, Lazy lambda calculus: theories, models and local structure characterization (extended abstract), 487-498 [Zbl 1425.68055]
Laenens, Els; Vermeir, Dirk; Zaniolo, Carlo, Logic programming semantics made easy, 499-508 [Zbl 1425.68052]
Debray, Saumya K., On the complexity of dataflow analysis of logic programs, 509-520 [Zbl 1425.68050]
Cortesi, Agostino; Filé, Gilberto; Winsborough, William, Comparison of abstract interpretations, 521-532 [Zbl 1425.68066]
Phoa, Wesley; Fourman, Michael, A proposed categorical semantics for pure ML, 533-544 [Zbl 1425.68243]
Henzinger, Thomas A.; Manna, Zohar; Pnueli, Amir, What good are digital clocks?, 545-558 [Zbl 1425.68255]
Moller, Faron; Tofts, Chris, Behavioural abstraction in TCCS, 559-570 [Zbl 1425.68299]
Brown, Carolyn; Gurr, Doug, Timing Petri nets categorically, 571-582 [Zbl 1425.68287]
Gastin, Paul; Petit, Antoine, Asynchronous cellular automata for infinite traces, 583-594 [Zbl 1425.68281]
Hoogers, P. W.; Kleijn, H. C. M.; Thiagarajan, P. S., A trace semantics for Petri nets (extended abstract), 595-604 [Zbl 1427.68199]
Vogler, Walter, Asynchronous communication of Petri nets and the refinement of transitions, 605-616 [Zbl 1425.68303]
Montanari, Ugo; Yankelevich, Daniel, A parametric approach to localities, 617-628 [Zbl 1427.68207]
Degano, Pierpaolo; Priami, Corrado, Proved trees, 629-640 [Zbl 1425.68291]
Olderog, Ernst-Rüdiger, Interfaces between languages for communicating systems, 641-655 [Zbl 1425.68300]
Sannella, Donald; Tarlecki, Andrzej, Toward formal development of programs from algebraic specifications: model-theoretic foundations, 656-671 [Zbl 1425.68082]
Fix, Limor; Francez, Nissim; Grumberg, Orna, Program composition via unification, 672-684 [Zbl 1427.68045]
Milner, Robin; Sangiorgi, Davide, Barbed bisimulation, 685-695 [Zbl 1425.68298]
Rabinovich, Alexander, Checking equivalences between concurrent systems of finite agents (extended abstract), 696-707 [Zbl 1425.68302]
Cleaveland, Rance; Smolka, Scott A.; Zwarico, Amy, Testing preorders for probabilistic processes, 708-719 [Zbl 1425.68289]


68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Nxx Theory of software
68Qxx Theory of computing
00B25 Proceedings of conferences of miscellaneous specific interest


Zbl 0753.00027
Full Text: DOI