Automata, Languages and Programming / 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000. Proceedings / Ugo Montanari (u. a.) / Taschenbuch / Englisch / 2000 - Taschenbuch

EAN (ISBN-13): 9783540677154
ISBN (ISBN-10): 3540677151
Gebundene Ausgabe
Taschenbuch
Erscheinungsjahr: 2000
Herausgeber: Springer Berlin

Buch in der Datenbank seit 2007-11-17T19:51:52+01:00 (Vienna)
Detailseite zuletzt geändert am 2023-01-07T17:38:02+01:00 (Vienna)
ISBN/EAN: 9783540677154

ISBN - alternative Schreibweisen:
3-540-67715-1, 978-3-540-67715-4
Alternative Schreibweisen und verwandte Suchbegriffe:
Autor des Buches: welzl, montanari, goos, emo
Titel des Buches: proceedings the international colloquium language, automata languages and programming, welcome switzerland, lecture notes computer science automata

---

Daten vom Verlag:

Autor/in: Ugo Montanari; Jose D.P. Rolim; Emo Welzl
Titel: Lecture Notes in Computer Science; Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000 Proceedings
Verlag: Springer; Springer Berlin
952 Seiten
Erscheinungsjahr: 2000-06-28
Berlin; Heidelberg; DE
Sprache: Englisch
106,99 € (DE)
109,99 € (AT)
118,00 CHF (CH)
Available
XVI, 952 p.

BC; Hardcover, Softcover / Informatik, EDV/Informatik; Theoretische Informatik; Verstehen; Automat; algorithms; automata; complexity; computer; computer science; logic; programming; Theory of Computation; Software Engineering; Computer Communication Networks; Special Purpose and Application-Based Systems; Mathematics of Computing; Software Engineering; Netzwerk-Hardware; Wissensbasierte Systeme, Expertensysteme; Mathematik für Informatiker; EA

Invited Talk.- Game Semantics: Achievements and Prospects.- Clique Is Hard to Approximate within n 1-o(1).- Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time.- Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming.- A Statically Allocated Parallel Functional Language.- An Optimal Minimum Spanning Tree Algorithm.- Improved Shortest Paths on the Word RAM.- Improved Algorithms for Finding Level Ancestors in Dynamic Trees.- Lax Logical Relations.- Reasoning about Idealized ALGOL Using Regular Languages.- The Measurement Process in Domain Theory.- Invited Talk.- Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution.- Monotone Proofs of the Pigeon Hole Principle.- Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models.- Algebraic Models for Contextual Nets.- Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.- Measures of Nondeterminism in Finite Automata.- LTL Is Expressively Complete for Mazurkiewicz Traces.- An Automata-Theoretic Completeness Proof for Interval Temporal Logic.- Invited Talk.- Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?.- Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search.- Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices.- Variable Independence, Quantifier Elimination, and Constraint Representations.- Constraint Satisfaction Problems and Finite Algebras.- An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing.- Resource Augmentation for Online Bounded Space Bin Packing.- Optimal Projective Algorithms for the List Update Problem.- Efficient Verification Algorithms for One-Counter Processes.- On theComplexity of Bisimulation Problems for Basic Parallel Processes.- Decidable First-Order Transition Logics for PA-Processes.- Invited Talk.- Non Interference for the Analysis of Cryptographic Protocols.- Average Bit-Complexity of Euclidean Algorithms.- Planar Maps and Airy Phenomena.- Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System.- Information Flow vs. Resource Access in the Asynchronous Pi-Calculus (Extended Abstract).- Award Talk.- The Genomics Revolution and Its Challenges for Algorithmic Research.- Invited Talk.- Alternating the Temporal Picture for Safety.- Necessary and Sufficient Assumptions for Non-interactive Zero-Knowledge Proofs of Knowledge for All NP Relations.- Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP.- A New Unfolding Approach to LTL Model Checking.- Reasoning about Message Passing in Finite State Environments.- Extended Notions of Security for Multicast Public Key Cryptosystems.- One-Round Secure Computation and Secure Autonomous Mobile Agents.- Round-Optimal and Abuse-Free Optimistic Multi-party Contract Signing.- On the Centralizer of a Finite Set.- On the Power of Tree-Walking Automata.- Determinization of Transducers over Infinite Words.- Invited Talk.- Constraint Programming and Graph Algorithms.- Scalable Secure Storage when Half the System Is Faulty.- Generating Partial and Multiple Transversals of a Hypergraph.- Revisiting the Correspondence between Cut Elimination and Normalisation.- Negation Elimination from Simple Equational Formulae.- Hardness of Set Cover with Intersection 1.- Strong Inapproximability of the Basic k-Spanner Problem.- Infinite Series-Parallel Posets: Logic and Languages.- On Deciding if Deterministic Rabin Language Is inBüchi Class.- On Message Sequence Graphs and Finitely Generated Regular MSC Languages.- Invited Talk.- Pseudorandomness.- A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.- Deterministic Radio Broadcasting.- An ?-Complete Equational Specification of Interleaving.- A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors.- Tight Size Bounds for Packet Headers in Narrow Meshes.- Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link.- On the Logical Characterisation of Performability Properties.- On the Representation of Timed Polyhedra.- Invited Talk.- Min-wise Independent Permutations: Theory and Practice.- Testing Acyclicity of Directed Graphs in Sublinear Time.- Computing the Girth of a Planar Graph.- Lower Bounds Are Not Easier over the Reals: Inside PH.- Unlearning Helps.- Fast Approximation Schemes for Euclidean Multi-connectivity Problems.- Approximate TSP in Graphs with Forbidden Minors.- Polynomial Time Approximation Schemes for General Multiprocessor Job Shop Scheduling.- The Many Faces of a Translation.- Gales and the Constructive Dimension of Individual Sequences.- The Global Power of Additional Queries to p-Random Oracles.- Homogenization and the Polynomial Calculus.