Peter Widmayer / Francisco Triguero / Rafael Morales / Matthew Hennessy / Stephan Eidenbenz / Ricardo Conejo (eds.)
Automata, Languages and Programming
29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002. Proceedings
Herausgegeben:Widmayer, Peter; Triguero, Francisco; Morales, Rafael; Hennessy, Matthew; Eidenbenz, Stephan; Conejo, Ricardo
Peter Widmayer / Francisco Triguero / Rafael Morales / Matthew Hennessy / Stephan Eidenbenz / Ricardo Conejo (eds.)
Automata, Languages and Programming
29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002. Proceedings
Herausgegeben:Widmayer, Peter; Triguero, Francisco; Morales, Rafael; Hennessy, Matthew; Eidenbenz, Stephan; Conejo, Ricardo
- Broschiertes Buch
- Merkliste
- Auf die Merkliste
- Bewerten Bewerten
- Teilen
- Produkt teilen
- Produkterinnerung
- Produkterinnerung
This volume contains the contributions of the 29th International Colloquium on Automata, Languages, and Programming (ICALP) held July8 13, 2002 in M alaga, Spain. The diversityand the qualityof the scienti?c program of ICALP 2002 serve as evidence that theoretical computer science with all its aspects continues to be a vibrant ?eld and is increasinglyturning into a valuable and abundant source of ideas and concepts for other research disciplines and app- cations. ICALP has been the main annual scienti?c event of the European Assoc- tion for Theoretical Computer Science (EATCS) for almost…mehr
This volume contains the contributions of the 29th International Colloquium on Automata, Languages, and Programming (ICALP) held July8 13, 2002 in M alaga, Spain. The diversityand the qualityof the scienti?c program of ICALP 2002 serve as evidence that theoretical computer science with all its aspects continues to be a vibrant ?eld and is increasinglyturning into a valuable and abundant source of ideas and concepts for other research disciplines and app- cations. ICALP has been the main annual scienti?c event of the European Assoc- tion for Theoretical Computer Science (EATCS) for almost thirtyyears, making ICALP one of the best-established conferences in theoretical computer science and EATCS one of the world s largest and oldest theoretical computer science organizations. To re?ect the two parts of the EATCS journal Theoretical Computer Science (TCS), ICALP s technical program is split into two parts: while track A is - voted to algorithms, automata, complexity, and games, track B focuses on logic, semantics, and theoryof programming.
Produktdetails
- Produktdetails
- Lecture Notes in Computer Science 2380
- Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
- Artikelnr. des Verlages: 978-3-540-43864-9
- Seitenzahl: 1072
- Englisch
- Abmessung: 235mm x 155mm
- Gewicht: 1330g
- ISBN-13: 9783540438649
- ISBN-10: 3540438645
- Artikelnr.: 27538477
- Lecture Notes in Computer Science 2380
- Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
- Artikelnr. des Verlages: 978-3-540-43864-9
- Seitenzahl: 1072
- Englisch
- Abmessung: 235mm x 155mm
- Gewicht: 1330g
- ISBN-13: 9783540438649
- ISBN-10: 3540438645
- Artikelnr.: 27538477
Peter Widmayer ist als Programm-Manager für mySAP ERP tätig. Er repräsentiert die ERP-Entwicklung im mySAP ERP 2005 Ramp-up und ist zudem programmverantwortlich für die ERP-Mittelstandsinitiative. Davor führte er innerhalb der globalen ERP-Initiative den mySAP ERP 2004 Ramp-up zu weltweitem Erfolg. Seine umfassende SAP-Erfahrung gewann er während der Zeit als Verantwortlicher für den SAP-Produktstandard Globalisierung sowie während der Markteinführung der Unicode-Technologie zur Unterstützung globaler Sprachanforderungen. Als promovierter Experimentalphysiker begann er 1999 bei der SAP AG. Er verbrachte die ersten Jahre als Applikations- und Technologieberater für internationale Konzernkunden.
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.- TheQuest 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.
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.- TheQuest 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.