+612 9045 4394
Automata, Languages and Programming : 24th International Colloquium, ICALP'97, Bologna, Italy, July 7-11, 1997: Proceedings :  24th International Colloquium, ICALP'97, Bologna, Italy, July 7-11, 1997: Proceedings - Pierpaolo Degano

Automata, Languages and Programming : 24th International Colloquium, ICALP'97, Bologna, Italy, July 7-11, 1997: Proceedings

24th International Colloquium, ICALP'97, Bologna, Italy, July 7-11, 1997: Proceedings


Published: July 1997
Ships: 5 to 9 business days
5 to 9 business days
or 4 easy payments of $51.04 with Learn more

This book constitutes the refereed proceedings of the 24th International Colloquium on Automata, Languages and Programming, ICALP '97, held in Bologna, Italy, in July 1997. ICALP '97 celebrated the 25th anniversary of the European Association for Theoretical Computer Science (EATCS), which has sponsored the ICALP meetings since 1972.The volume presents 73 revised full papers selected from a total of 197 submissions. Also included are six invited contributions. ICALP is one of the few flagship conferences in the area. The book addresses all current topics in theoretical computer science.

Graphical Calculi for Interactionp. 1
NP-Completeness: A Retrospectivep. 2
The LEDA Platform for Combinatorial and Geometric Computingp. 7
The Wadge-Wegner Hierarchy of [omega]-rational Setsp. 17
From Chaotic Iteration to Constraint Propagationp. 36
DNA[superscript 2]DNA Computations: A Potential "Killer App"?p. 56
Tilings and Quasiperiodicityp. 65
Enumerative Sequences of Leaves in Rational Treesp. 76
A Completion Algorithm for Codes with Bounded Synchronization Delayp. 87
The Expressibility of Languages and Relations by Word Equationsp. 98
Finite Loops Recognize Exactly the Regular Open Languagesp. 110
An Abstract Data Type for Real Numbersp. 121
Recursive Computational Depthp. 132
Some Bounds on the Computational Power of Piecewise Constant Derivative Systemsp. 143
Monadic Simultaneous Rigid E-Unification and Related Problemsp. 154
Computability on the Probability Measures on the Borel Sets of the Unit Intervalp. 166
Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-offsp. 177
Results on Resource-Bounded Measurep. 188
Randomization and Nondeterminism are Incomparable for Ordered Read-Once Branching Programsp. 195
Checking Properties of Polynomialsp. 203
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NPp. 214
Game Theoretic Analysis of Call-by-value Computationp. 225
On Modular Properties of Higher Order Extensional [lambda]-Calculip. 237
On Explicit Substitutions and Namesp. 248
On the Dynamics of Sharing Graphsp. 259
Minimizing Diameters of Dynamic Treesp. 270
Improving Spanning Trees by Upgrading Nodesp. 281
Dynamic Algorithms of Graphs of Bounded Treewidthp. 292
The Name Discipline of Uniform Receptivenessp. 303
On Confluence in the [pi]-calculusp. 314
A Proof Theoretical Approach to Communicationp. 325
Solving Trace Equations Using Lexicographical Normal Formsp. 336
Star-Free Picture Expressions are Strictly Weaker than First-Order Logicp. 347
An Algebra-Based Method to Associate Rewards with EMPA Termsp. 358
A Semantics Preserving Actor Translationp. 369
Periodic and Non-periodic Min-Max Equationsp. 379
Efficient Parallel Graph Algorithms for Coarse Grained Multicomputers and BSPp. 390
Upper Bound on the Communication Complexity of Private Information Retrievalp. 401
Computation Paths Logic: An Expressive, yet Elementary, Process Logicp. 408
Model Checking the Full Modal Mu-Calculus for Infinite Sequential Processesp. 419
Symbolic Model Checking for Probabilistic Processesp. 430
On the Concentration of the Height of Binary Search Treesp. 441
An Improved Master Theorem for Divide-and-Conquer Recurrencesp. 449
Bisimulation for Probabilistic Transition Systems: A Coalgebraic Approachp. 460
Distributed Processes and Location Failuresp. 471
Basic Observables for Processesp. 482
Constrained Bipartite Edge Coloring with Applications to Wavelength Routingp. 493
Colouring Paths in Directed Symmetric Trees with Applications to WDM Routingp. 505
On-Line Routing in All-Optical Networksp. 516
A Complete Characterization of the Path Layout Construction Problem for ATM Networks with Given Hop Count and Loadp. 527
Efficiency of Asynchronous Systems and Read Arcs in Petri Netsp. 538
Bisimulation Equivalence is Decidable for One-Counter Processesp. 549
Symbolic Reachability Analysis of FIFO-Channel Systems with Nonregular Sets of Configurationsp. 560
Axiomatizations for the Perpetual Loop in Process Algebrap. 571
Discrete-Time Control for Rectangular Hybrid Automatap. 582
Maintaining Minimum Spanning Trees in Dynamic Graphsp. 594
Efficient Splitting and Merging Algorithms for Order Decomposable Problemsp. 605
Efficient Array Partitioningp. 616
Constructive Linear Time Algorithms for Brandwidthp. 627
The Word Matching Problem is Undecidable for Finite Special String-Rewriting Systems that are Confluentp. 638
The Geometry of Orthogonal Reduction Spacesp. 649
The Theory of Vaccinesp. 660
The Equivalence Problem for Deterministic Pushdown Automata is Decidablep. 671
On Recognizable and Rational Formal Power Series in Partially Commuting Variablesp. 682
On a Conjecture of J. Shallitp. 693
On Characterizations of Escrow Encryption Schemesp. 705
Randomness-Efficient Non-Interactive Zero Knowledgep. 716
Approximation Results for the Optimum Cost Chromatic Partition Problemp. 727
The Minimum Color Sum of Bipartite Graphsp. 738
A Primal-Dual Approach to Approximation of Node-Deletion Problems for Matroidal Propertiesp. 749
Independent Sets in Asteroidal Triple-Free Graphsp. 760
Refining and Compressing Abstract Domainsp. 771
Labelled Reductions, Runtime Errors, and Operational Subsumptionp. 782
A Complete and Efficiently Computable Topological Classification of D-dimensional Linear Cellular Automata over Z[subscript m]p. 794
Recognizability Equals Definability for Partial k-Pathsp. 805
Molecular Computing, Bounded Nondeterminism, and Efficient Recursionp. 816
Constructing Big Trees from Short Sequencesp. 827
Termination of Constraint Logic Programsp. 838
The Expressive Power of Unique Total Stable Model Semanticsp. 849
Author Indexp. 861
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540631651
ISBN-10: 3540631658
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 864
Published: July 1997
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 4.45
Weight (kg): 1.21