19. ICALP 1992: Vienna, Austria

Werner Kuich (Ed.): Automata, Languages and Programming, 19th International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992, Proceedings. Lecture Notes in Computer Science 623 Springer 1992, ISBN 3-540-55719-9

Complexity

Ming Li, Paul M. B. Vitányi: Philosophical Issues in Kolmogorov Complexity. 1-15
Howard Straubing: Circuit Complexity and the Expressive Power of Generalized First-Order Formulas. 16-27
Alfredo De Santis, Giuseppe Persiano, Moti Yung: One-Message Statistical Zero-Knowledge Proofs and Space-Bounded Verifier. 28-40

Formal Languages

Veikko Keränen: Abelian Squares are Avoidable on 4 Letters. 41-52
Juhani Karhumäki, Wojciech Plandowski, Wojciech Rytter: Polynomial Size Test Sets for Context-Free Languages. 53-64
Taishin Y. Nishida: Quasi-Deterministic 0L Systems. 65-76
Gerhard Buntrock, Krzysztof Lorys: On Growing Context-Sensitive Languages. 77-88

Finite Automata

Jeffrey Shallit: Numeration Systems, Linear Recurrences, and Regular Sets (Extended Abstract). 89-100
Daniel Krob: The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable. 101-112
Mireille Clerbout, Yves Roos, Wieslaw Zielonka: Semi-Commutations and Rational Expressions. 113-125
Oscar H. Ibarra, Nicholas Q. Trân: New Results Concerning Synchronized Finite Automata. 126-137

Graph Grammars and Complexity

Joost Engelfriet: A Greibach Normal Form for Context-free Graph Grammars. 138-149
Pierre Péladeau, Andreas Podelski: On Reverse and General Definite Tree Languages (Extended Abstract). 150-161
Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf: Reductions to Sets of Low Information Content. 162-173
Ming-Jye Sheu, Timothy J. Long: UP and the Low and High Hierarchies: A Relativized Separation. 174-185

Algorithm Analysis

Philippe Flajolet: Analytic Analysis of Algorithms. 186-210
Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski: How to Count Quickly and Accurately: A Unified Analysis of Probabilistic Counting and Other Related Problems. 211-222
Ulrich Schmid: The Average CRI-Length of a Tree Collision Resolution Algorithm in Presence of Multiplicity-Dependent Capture Effects. 223-234

Algorithms

Martin Dietzfelbinger, Joseph Gil, Yossi Matias, Nicholas Pippenger: Polynomial Hash Functions Are Reliable (Extended Abstract). 235-246
R. C. Sekar, R. Ramesh, I. V. Ramakrishnan: Adaptive Pattern Matching. 247-260
Yishay Mansour: Randomized Interpolation and Approximation of Sparse Polynomials. 261-272
Hans L. Bodlaender, Michael R. Fellows, Tandy Warnow: Two Strikes Against Perfect Phylogeny. 273-283

Parallel Computation

Guo-Qiang Zhang: Disjunctive Systems and L-Domains. 284-295
Alberto Apostolico, Dany Breslauer, Zvi Galil: Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract). 296-307
Andrei Z. Broder, Alan M. Frieze, Eli Shamir, Eli Upfal: Near-perfect Token Distribution. 308-317
Torben Hagerup: Fast Integer Merging on the EREW PRAM. 318-329

Graph Algorithms

Samir Khuller, Ramakrishna Thurimella: Approximation Algorithms for Graph Augmentation. 330-341
Jeffery Westbrook: Fast Incremental Planarity Testing. 342-353
Johannes A. La Poutré: Maintenance of Triconnected Components of Graphs (Extended Abstract). 354-365
Vijay V. Vazirani, Mihalis Yannakakis: Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract). 366-377

Symbolic Computation

Bruno Buchberger: Gröbner Bases: An Introduction. 378-379
Reinhard Bündgen: Buchberger's Algorithm: The Term Rewriter's Point of View (Extended Abstract). 380-391
Hubert Comon: Completion of Rewrite Systems with Membership Constraints. 392-403

Geometric Algorithms

Günter Rote: A New Metric Between Polygons and How to Compute it. 404-415
Mike Paterson, F. Frances Yao: On Nearest-Neighbor Graphs. 416-426
Jirí Matousek, Raimund Seidel: A Tail Estimate for Mulmuley's Segment Intersection Algorithm. 427-438
Bernard Chazelle, Burton Rosenberg: Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine. 439-449

Logic and Models I

Phokion G. Kolaitis, Moshe Y. Vardi: Infinitary Logic for Computer Science. 450-473
Edward Y. Chang, Zohar Manna, Amir Pnueli: Characterization of Temporal Property Classes. 474-486
C.-H. Luke Ong: Lazy Lambda Calculus: Theories, Models and Local Structure Characterization (Extended Abstract). 487-498

Logic and Models II

Els Laenens, Dirk Vermeir, Carlo Zaniolo: Logic Programming Semantics Made Easy. 499-508
Saumya K. Debray: On the Complexity of Dataflow Analysis of Logic Programs. 509-520
Agostino Cortesi, Gilberto Filé, William H. Winsborough: Comparison of Abstract Interpretations. 521-532
Wesley Phoa, Michael P. Fourman: A Proposed Categorial Semantics for Pure ML. 533-544

Time Specification

Thomas A. Henzinger, Zohar Manna, Amir Pnueli: What Good Are Digital Clocks? 545-558
Faron Moller, Chris M. N. Tofts: Behavioural Abstraction in TCCS. 559-570
Carolyn Brown, Doug Gurr: Timing Petri Nets Categorically. 571-582
Paul Gastin, Antoine Petit: Asynchronous Cellular Automata for Infinite Traces. 583-594

Concurrency Semantics

P. W. Hoogers, H. C. M. Kleijn, P. S. Thiagarajan: A Trace Semantics for Petri Nets (Extended Abstract). 595-604
Walter Vogler: Asynchronous Communication of Petri Nets and the Refinement of Transitions. 605-616
Ugo Montanari, Daniel Yankelevich: A Parametric Approach to Localities. 617-628
Pierpaolo Degano, Corrado Priami: Proved Trees. 629-640

Program Development

Ernst-Rüdiger Olderog: Interfaces between Languages for Communicating Systems. 641-655
Donald Sannella, Andrzej Tarlecki: Towards Formal Development of Programs from Algebraic Specifications: Model-Theoretic Foundations. 656-671

Program Equivalences

Limor Fix, Nissim Francez, Orna Grumberg: Program Composition via Unification. 672-684
Robin Milner, Davide Sangiorgi: Barbed Bisimulation. 685-695
Alexander Moshe Rabinovich: Checking Equivalences Between Concurrent Systems of Finite Agents (Extended Abstract). 696-707
Rance Cleaveland, Scott A. Smolka, Amy E. Zwarico: Testing Preorders for Probabilistic Processes. 708-719