Automata, Languages and Programming [[electronic resource] ] : 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002. Proceedings / / edited by Peter Widmayer, Francisco Triguero, Rafael Morales, Matthew Hennessy, Stephan Eidenbenz, Ricardo Conejo

• Pubblicazione: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002
• Edizione: 1st ed. 2002.
• Descrizione fisica: 1 online resource (XLII, 1072 p.)
• Disciplina: 511.3
• Soggetto topico: Artificial intelligence; Software engineering; Control engineering; Computers; Computer science—Mathematics; Computer graphics; Artificial Intelligence; Software Engineering/Programming and Operating Systems; Control and Systems Theory; Theory of Computation; Mathematics of Computing; Computer Graphics
• Persona (resp. second.): WidmayerPeter; TrigueroFrancisco; MoralesRafael; HennessyMatthew; EidenbenzStephan; ConejoRicardo
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references at the end of each chapters and index.
• Nota di contenuto: Invited Talks -- Molecular Assembly and Computation: From Theory to Experimental Demonstrations -- Towards a Predictive Computational Complexity Theory -- Equivariant Syntax and Semantics -- L(A) = L(B)? Decidability Results from Complete Formal Systems -- Discrete Tomography: Reconstruction under Periodicity Constraints -- Local and Global Methods in Data Mining: Basic Techniques and Open Problems -- Program Debugging and Validation Using Semantic Approximations and Partial Specifications -- Best Papers -- Inapproximability Results for Equations over Finite Groups -- A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs -- On Families of Graphs Having a Decidable First Order Theory with Reachability -- Contributions -- Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet -- The Structure and Complexity of Nash Equilibria for a Selfish Routing Game -- Control Message Aggregation in Group Communication Protocols -- Church-Rosser Languages vs. UCFL -- Intersection of Regular Languages and Star Hierarchy -- On the Construction of Reversible Automata for Reversible Languages -- Priority Queues, Pairing, and Adaptive Sorting -- Exponential Structures for Efficient Cache-Oblivious Algorithms -- Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations -- On the Complexity of Resolution with Bounded Conjunctions -- Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes -- Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials -- Exponential Lower Bound for Static Semi-algebraic Proofs -- Paths Problems in Symmetric Logarithmic Space -- Scheduling Search Procedures -- Removable Online Knapsack Problems -- New Bounds for Variable-Sized and Resource Augmented Online Bin Packing -- The Quest for Small Universal Cellular Automata -- Hyperbolic Recognition by Graph Automata -- Quantum and Stochastic Branching Programs of Bounded Width -- Spanning Trees with Bounded Number of Branch Vertices -- Energy Optimal Routing in Radio Networks Using Geometric Data Structures -- Gossiping with Bounded Size Messages in ad hoc Radio Networks -- The Kolmogorov-Loveland Stochastic Sequences Are Not Closed under Selecting Subsequences -- The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications -- Constraint Satisfaction Problems in Non-deterministic Logarithmic Space -- Cache Oblivious Distribution Sweeping -- One-Probe Search -- New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems -- Measuring the Probabilistic Powerdomain -- Games Characterizing Levy-Longo Trees -- Comparing Functional Paradigms for Exact Real-Number Computation -- Random Sampling from Boltzmann Principles -- On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures -- Bialgebraic Modelling of Timed Processes -- Testing Labelled Markov Processes -- Why Computational Complexity Requires Stricter Martingales -- Correspondence Principles for Effective Dimensions -- A Total Approach to Partial Algebraic Specification -- Axiomatising Divergence -- A Spatial Logic for Querying Graphs -- Improving Time Bounds on Maximum Generalised Flow Computations by Contracting the Network -- Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION -- Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths -- Synthesis of Uninitialized Systems -- Infinite-State High-Level MSCs: Model-Checking and Realizability -- Universal Inherence of Cycle-Free Context-Free Ambiguity Functions -- Histogramming Data Streams with Fast Per-Item Processing -- Finding Frequent Items in Data Streams -- Symbolic Strategy Synthesis for Games on Pushdown Graphs -- Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard -- Solving the String Statistics Problem in Time (nlogn) -- A PTAS for Distinguishing (Sub)string Selection -- On the Theory of One-Step Rewriting in Trace Monoids -- Navigating with a Browser -- Improved Results for Stackelberg Scheduling Strategies -- Call Control in Rings -- Preemptive Scheduling in Overloaded Systems -- The Equivalence Problem of Finite Substitutions on ab*c, with Applications -- Deciding DPDA Equivalence Is Primitive Recursive -- Two-Way Alternating Automata and Finite Models -- Approximating Huffman Codes in Parallel -- Seamless Integration of Parallelism and Memory Hierarchy -- The Communication Complexity of Approximate Set Packing and Covering -- Antirandomizing the Wrong Game -- Fast Universalization of Investment Strategies with Provably Good Relative Returns -- Randomized Pursuit-Evasion in Graphs -- The Essence of Principal Typings -- Complete and Tractable Local Linear Time Temporal Logics over Traces -- An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces -- Random Numbers and an Incomplete Immune Recursive Set -- A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers -- Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem -- Finding a Path of Superlogarithmic Length -- Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs -- Improved Inapproximability Results for Vertex Cover on k-Uniform Hypergraphs -- Efficient Testing of Hypergraphs -- Optimal Net Surface Problems with Applications -- Wagner’s Theorem on Realizers -- Circular Arrangements.
• Titolo autorizzato: Automata, languages and programming
• ISBN: 3-540-45465-9
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996465395103316
• Lo trovi qui: Univ. di Salerno
• Serie: Lecture Notes in Computer Science, . 0302-9743 ; ; 2380