22. ICALP 1995: Szeged, Hungary

Zoltán Fülöp, Ferenc Gécseg (Eds.): Automata, Languages and Programming, 22nd International Colloquium, ICALP95, Szeged, Hungary, July 10-14, 1995, Proceedings. Lecture Notes in Computer Science 944 Springer 1995, ISBN 3-540-60084-1

Concurrency I

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg:
Theory of 2-Structures. 1-14
Volker Diekert, Paul Gastin:
A Domain for Concurrent Termination: A Generalization of Mazurkiewicz Traces (Extended Abstract). 15-26
Zoltán Ésik, Michael Bertol:
Nonfinite Axiomatizability of the Equational Theory of Shuffle. 27-38

Werner Kuich:
The Algebraic Equivalent of AFL Theory. 39-50
Karel Culik II, Jarkko Kari:
Finite State Transformations of Images. 51-62
Marjo Lipponen:
Post Correspondence Problem: Words Possible as Primitive Solutions. 63-74
Yves Métivier, Gwénaël Richomme, Pierre-André Wacrenier:
Computing the Closure of Sets of Words Under Partial Commutations. 75-86

Hans L. Bodlaender, Babette de Fluiter:
Intervalizing k-Colored Graphs. 87-98
Zhi-Zhong Chen:
NC Algorithms for Finding a Maximal Set of Paths with Application to Compressing Strings. 99-110
Raffaele Giancarlo, Roberto Grossi:
On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications. 111-122
Andreas Parra, Petra Scheffler:
How to Use the Minimal Separators of a Graph for its Chordal Triangulation. 123-134

Jean-Claude Bermond, Luisa Gargano, Adele A. Rescigno, Ugo Vaccaro:
Fast Gossiping by Short Messages. 135-146
Feng Bao, Yoshihide Igarashi:
Break Finite Automata Public Key Cryptosystem. 147-158
Sotiris E. Nikoletseas, John H. Reif, Paul G. Spirakis, Moti Yung:
Stocastic Graphs Have Short Memory: Fully Dynamic Connectivity in Poly-Log Expected Time. 159-170
Carlo Blundo, Alfredo De Santis, Giuseppe Persiano, Ugo Vaccaro:
On the Number of Random Bits in Totally Private Computation. 171-182

Rusins Freivalds, Marek Karpinski:
Lower Time Bounds for Randomized Computation. 183-195
Johannes Köbler, Osamu Watanabe:
New Collapse Consequences of NP Having Small Circuits. 196-207
José L. Balcázar:
The Complexity of Searching Succinctly Represented Graphs. 208-219

Frank Bauernöppel, Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Marc Noy, Jörg-Rüdiger Sack, Jorge Urrutia:
Optimal Shooting: Characterizations and Applications. 220-231
Vincenzo Auletta, Domenico Parente, Giuseppe Persiano:
Placing Resources in a Tree: Dynamic and Static Algorithms. 232-243
Shiva Chaudhuri, Christos D. Zaroliagis:
Shortest Path Queries in Digraphs of Small Treewidth. 244-255
Mordecai J. Golin, Günter Rote:
A Dynamic Programming Algorithm for Constructing Optimal Refix-Free Codes for Unequal Letter Costs. 256-267

Hans L. Bodlaender, Torben Hagerup:
Parallel Algorithms with Optimal Speedup for Bounded Treewidth. 268-279
Monika Rauch Henzinger:
Approximating Minimum Cuts under Insertions. 280-291
Derek G. Corneil, Stephan Olariu, Lorna Stewart:
Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs. 292-302
Stefano Leonardi, Alberto Marchetti-Spaccamela:
On-line Resource Management with Applications to Routing and Scheduling. 303-314

H. Petersen:
Alternation in Simple Devices. 315-323
Thomas A. Henzinger:
Hybrid Automata with Finite Bisimulatioins. 324-335
Luis-Miguel Lopez, Philippe Narbel:
Generalized Sturmian Languages. 336-347
Jean-Eric Pin, Pascal Weil:
Polynomial Closure and Unambiguous Product. 348-359

Amir M. Ben-Amram, Zvi Galil:
Lower Bounds on Algebraic Random Access Machines (Extended Abstract). 360-371
Andrea Pietracaprina, Geppino Pucci:
Improved Deterministic PRAM Simulation on the Mesh. 372-383
Klaus Ambos-Spies:
On Optimal Polynomial Time Approximations: P-Levelability vs. Delta-Levelability (Extended Abstract). 384-392

Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo:
Weakly Useful Sequences. 393-404
Thomas Schwentick:
Graph Connectivity, Monadic NP and Built-in Relations of Moderate Degree. 405-416
Thomas A. Henzinger, Peter W. Kopke, Howard Wong-Toi:
The Expressive Power of Clocks. 417-428

Gheorghe Paun:
Grammar Systems: A Grammatical Approach to Distribution and Cooperation. 429-443
Tero Harju, Juhani Karhumäki, Wojciech Plandowski:
Compactness of Systems of Equations in Semigroups. 444-454
Pavol Duris, Zvi Galil:
Sensing Versus Nonsensing Automata. 455-463

Panayiotis Bozanis, Nectarios Kitsios, Christos Makris, Athanasios K. Tsakalidis:
New Upper Bounds for Generalized Intersection Searching Problems. 464-474
Bernd Becker, Rolf Drechsler, Michael Theobald:
OKFDDs versus OBDDs and OFDDs. 475-486
Madhav V. Marathe, R. Ravi, Ravi Sundaram, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt III:
Bicriteria Network Design Problems. 487-498
Ngoc-Minh Lê:
On Determining Optimal Strategies in Pursiut Games in the Plane. 499-510

Albert Rubio:
Extension Orderings. 511-522
Sergio Greco, Domenico Saccà, Carlo Zaniolo:
The PushDown Method to Optimize Chain Logic Programs (Extended Abstract). 523-534
Jørgen H. Andersen, Kåre J. Kristoffersen, Kim Guldstrand Larsen, Jesper Niedermann:
Automatic Synthesis of Real Time Systems. 535-546
Manuel Blum, Bruno Codenotti, Peter Gemmell, Troy Shahoumian:
Self-Correcting for Function Fields Transcendental Degree. 547-557

Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan:
Measure, Category and Learning Theory. 558-569
Michel Cosnard, Eric Goles Ch.:
A Characterization of the Existence of Energies for Neural Networks. 570-580
Helmut Jürgensen, Stavros Konstantinidis:
Variable-Length Codes for Error Correction. 581-592
Samir Khuller, Ehud Rivlin, Azriel Rosenfeld:
Graphbots: Mobility in Discrete Spaces. 593-604

Eike Best, Maciej Koutny:
Solving Recursive Net Equations. 605-623
Anuj Dawar, Lauri Hella, Phokion G. Kolaitis:
Implicit Definability and Infinitary Logic in Finite Model Theory. 624-635