19. ICALP 1992: Vienna, Austria
Werner Kuich (Ed.): Automata, Languages and Programming, 19th International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992, Proceedings. Springer 1992 Lecture Notes in Computer Science ISBN 3-540-55719-9
Complexity
- 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
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
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
- 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
- Torben Hagerup: Fast Integer Merging on the EREW PRAM. 318-329
Graph Algorithms
- 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
- 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
- C.-H. Luke Ong: Lazy Lambda Calculus: Theories, Models and Local Structure Characterization (Extended Abstract). 487-498
Logic and Models II
- 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
Time Specification
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
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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team