+612 9045 4394
Automata, Languages and Programming : 25th International Colloquium, ICALP `98, Aalborg, Denmark, July 13-17, 1998, Proceedings :  25th International Colloquium, ICALP `98, Aalborg, Denmark, July 13-17, 1998, Proceedings - Kim G. Larsen

Automata, Languages and Programming : 25th International Colloquium, ICALP `98, Aalborg, Denmark, July 13-17, 1998, Proceedings

25th International Colloquium, ICALP `98, Aalborg, Denmark, July 13-17, 1998, Proceedings

By: Kim G. Larsen (Editor), Sven Skyum (Editor), Glynn Winskel (Editor)


Published: September 1998
Ships: 5 to 9 business days
5 to 9 business days
or 4 easy payments of $56.98 with Learn more

This book constitutes the refereed proceedings of the 25th International Colloquium on Automata, Languages and Programming, ICALP'98, held in Aalborg, Denmark, in July 1998.The 70 revised full papers presented together with eight invited contributions were carefully selected from a total of 182 submissions. The book is divided in topical sections on complexitiy, verification, data structures, concurrency, computational geometry, automata and temporal logic, algorithms, infinite state systems, semantics, approximation, thorem proving, formal languages, pi-calculus, automata and BSP, rewriting, networking and routing, zero-knowledge, quantum computing, etc..

Algorithmic Verification of Linear Temporal Logic Specificationsp. 1
On Existentially First-Order Definable Languages and their Relation to NPp. 17
An Algebraic Approach to Communication Complexityp. 29
Deciding Global Partial-Order Propertiesp. 41
Simple Linear-Time Algorithms for Minimal Fixed Pointsp. 53
Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Methodp. 67
Simpler and Faster Dictionaries on the AC[superscript 0] RAMp. 79
Partial-Congruence Factorization of Bisimilarity Induced by Open Mapsp. 91
Reset Nets Between Decidability and Undecidabilityp. 103
Geometric Algorithms for Robotic Manipulationp. 116
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parenthesesp. 118
Reducing Simple Polygons to Triangles - A Proof For an Improved Conjecturep. 130
Difficult Configurations - On the Complexity of LTrLp. 140
On the Expressiveness of Real and Integer Arithmetic Automatap. 152
Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Treesp. 164
Independent Sets with Domination Constraintsp. 176
Robust Asynchronous Protocols Are Finite-Statep. 188
Deciding Bisimulation-Like Equivalences with Finite-State Processesp. 200
Do Probabilistic Algorithms Outperform Deterministic Ones?p. 212
A Degree-Decreasing Lemma for (MOD q, MOD p) Circuitsp. 215
Improved Pseudorandom Generators for Combinatorial Rectanglesp. 223
Translation Validation for Synchronous Languagesp. 235
An Efficient and Unified Approach to the Decidability of Equivalence of Propositional Programsp. 247
On Branching Programs With Bounded Uncertaintyp. 259
CONS-Free Programs with Tree Inputp. 271
Concatenable Graph Processes: Relating Processes and Derivation Tracesp. 283
Axioms for Contextual Net Processesp. 296
Existential Types: Logical Relations and Operational Equivalencep. 309
Optimal Sampling Strategies in Quicksortp. 327
A Genuinely Polynomial-Time Algorithm for Sampling Two-Rowed Contingency Tablesp. 339
A Modular Approach to Denotational Semanticsp. 351
Generalised Flowcharts and Gamesp. 363
Efficient Minimization of Numerical Summation Errorsp. 375
Efficient Approximation Algorithms for the Subset-Sums Equality Problemp. 387
Structural Recursive Definitions in Type Theoryp. 397
A Good Class of Tree Automata. Application to Inductive Theorem Provingp. 409
Locally Periodic Infinite Words and a Chaotic Behaviourp. 421
Bridges for Concatenation Hierarchiesp. 431
Complete Proof Systems for Observation Congrnences in Finite-Control [pi]-Calculusp. 443
Concurrent Constraints in the Fusion Calculusp. 455
On Computing the Entropy of Cellular Automatap. 470
On the Determinization of Weighted Finite Automatap. 482
Bulk-Synchronous Parallel Multiplication of Boolean Matricesp. 494
A Complex Example of a Simplifying Rewrite Systemp. 507
On a Duality between Kruskal and Dershowitz Theoremsp. 518
A Total AC-Compatible Reduction Ordering on Higher-Order Termsp. 530
Model Checking Game Properties of Multi-agent Systemsp. 543
Limited Wavelength Conversion in All-Optical Tree Networksp. 544
Computing Mimicking Networksp. 556
Metric Semantics for True Concurrent Real Timep. 568
The Regular Real-Time Languagesp. 580
Static and Dynamic Low-Congested Interval Routing Schemesp. 592
Low-Bandwidth Routing and Electrical Power Networksp. 604
Constraint Automata and the Complexity of Recursive Subtype Entailmentp. 616
Reasoning about the Past with Two-Way Automatap. 628
A Neuroidal Architecture for Cognitive Computationp. 642
Deterministic Polylog Approximation for Minimum Communication Spanning Treesp. 670
A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivityp. 682
Global/Local Subtyping and Capability Inference for a Distributed [pi]-Calculusp. 695
Checking Strong/Weak Bisimulation Equivalences and Observation Congruence for the [pi]-Calculusp. 707
Inversion of Circulant Matrices over Z[subscript m]p. 719
Application of Lempel-Ziv Encodings to the Solution of Word Equationsp. 731
Explicit Substitutions for Constructive Necessityp. 743
The Relevance of Proof-Irrelevancep. 755
New Horizons in Quantum Information Processingp. 769
Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NPp. 772
Image Density is Complete for Non-Interactive-SZKp. 784
Randomness Spacesp. 796
Totality, Definability and Boolean Circuitsp. 808
Quantum Countingp. 820
On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biologyp. 832
A Hierarchy of Equivalences for Asynchronous Calculip. 844
On Asynchrony in Name Passing Calculip. 856
Protection in Programming-Language Translationsp. 868
Efficient Simulations by Queue Machinesp. 884
Power of Cooperation and Multihead Finite Systemsp. 896
A Simple Solution to Type Specializationp. 908
Multi-Stage Programming: Axiomatization and Type Safetyp. 918
Author Indexp. 931
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540647812
ISBN-10: 3540647813
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 936
Published: September 1998
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 4.78
Weight (kg): 1.31