Automata, Languages and Programming: Seventh Colloquium Noordwijkerhout, the Netherlands July 14–18, 1980

W. Ainhirn (auth.), Jaco de Bakker, Jan van Leeuwen (eds.)3540100032, 9783540100034

This book constitutes the refereed proceedings of the 28th International Colloquium on Automata, Languages and Programming, ICALP 2001, held in Crete, Greece in July 2001. The 80 revised papers presented together with two keynote contributions and four invited papers were carefully reviewed and selected from a total of 208 submissions. The papers are organized in topical sections on algebraic and circuit complexity, algorithm analysis, approximation and optimization, complexity, concurrency, efficient data structures, graph algorithms, language theory, codes and automata, model checking and protocol analysis, networks and routing, reasoning and verification, scheduling, secure computation, specification and deduction, and structural complexity.

---

Table of contents :
How to get rid of pseudoterminals….Pages 1-11
Test sets for homomorphism equivalence on context free languages….Pages 12-18
Languages with homomorphic replacements….Pages 19-29
Functions equivalent to integer multiplication….Pages 30-37
Languages with reducing reflexive types….Pages 38-50
Semantics of unbounded nondeterminism….Pages 51-63
A shifting algorithm for min-max tree partitioning….Pages 64-75
A characterisation of computable data types by means of a finite equational specification method….Pages 76-90
A note on sweeping automata….Pages 91-97
Border rank of a p×q×2 tensor and the optimal approximation of a pair of bilinear forms….Pages 98-108
Derivations et reductions dans les grammaires algebrioues….Pages 109-118
Semantic analysis of communicating sequential processes….Pages 119-133
Dos systems and languages….Pages 134-141
Algebraic implementation of abstract data types: concept, syntax, semantics and correctness….Pages 142-156
Parameterized data types in algebraic specification languages….Pages 157-168
Characterizing correctness properties of parallel programs using fixpoints….Pages 169-181
Formal properties of one-visit and multi-pass attribute grammars (extended abstract)….Pages 182-194
Cryptocomplexity and NP-completeness….Pages 195-207
On the analysis of tree-matching algorithms….Pages 208-219
Generating and searching sets induced by networks….Pages 221-233
The complexity of the inequivalence problem for regular expressions with intersection….Pages 234-245
An almost linear time algorithm for computing a dependency basis in a relational data base….Pages 246-256
Bipolar synchronization systems….Pages 257-272
Testing of properties of finite algebras….Pages 273-281
A transaction model….Pages 282-298
On observing nondeterminism and concurrency….Pages 299-309
Terminal algebra semantics and retractions for abstract data types….Pages 310-323
The complexity of semilinear sets….Pages 324-337
A theory of nondeterminism….Pages 338-350
A representation theorem for models of *-free PDL….Pages 351-362
Present-day Hoare-like systems for programming languages with procedures: Power, limits and most likely extensions….Pages 363-373
Symmertric space-bounded computation (extended abstract)….Pages 374-384
On some properties of local testability….Pages 385-393
Semantics :Algebras,fixed points,axioms….Pages 394-408
Measuring the expressive power of dynamic logics: An application of abstract model theory….Pages 409-421
Pebbling mountain ranges and its application to DCFL-recognition….Pages 422-435
Space-restricted attribute grammars….Pages 436-448
A constructive approach to compiler correctness….Pages 449-469
A worst-case analysis of nearest neighbor searching by projection….Pages 470-482
Proprietes syntactiques du produit non ambigu….Pages 483-499
On the optimal assignment of attributes to passes in multi-pass attribute evaluators….Pages 500-511
Optimal unbounded search strategies….Pages 512-530
A “fast implementation” of a multidimensional storage into a tree storage….Pages 531-542
Grammatical families….Pages 543-554
Partitioned chain grammars….Pages 555-568
An improved program for constructing open hash tables….Pages 569-581
On the power of commutativity in cryptography….Pages 582-595
Characterizations of the LL(k) property….Pages 596-608
Computability in categories….Pages 609-620
On the size complexity of monotone formulas….Pages 621-631
Reversible computing….Pages 632-644
The use of metasystem transition in theorem proving and program optimization….Pages 645-657
On the power of real-time turing machines under varying specifications….Pages 658-671