Automata, Languages And Programming: Seventh Colloquium, Noordwijkerhout, The Netherlands, July 14-18, 1980. Proceedings (lecture Notes In Computer Science)

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. 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