Automata, Languages and Programming, 2 Teile

Optimal Branch-Decomposition of Planar Graphs in O(n 3) Time.- Automata and Formal Languages I.- NFAs With and Without ?-Transitions.- On the Equivalence of -Automata.- A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata.- Groupoids That Recognize Only Regular Languages.- Signature and Message Authentication.- Append-Only Signatures.- Hierarchical Group Signatures.- Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction.- Single-Key AIL-MACs from Any FIL-MAC.- Algorithmic Game Theory.- The Efficiency and Fairness of a Fixed Budget Resource Allocation Game.- Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability.- Automata and Logic.- Weighted Automata and Weighted Logics.- Restricted Two-Variable FO + MOD Sentences, Circuits and Communication Complexity.- Computational Algebra.- Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y 2=x +ax.- Solvability of a System of Bivariate Polynomial Equations over a Finite Field.- Cache-Oblivious Algorithms and Algorithmic Engineering.- Cache-Oblivious Planar Shortest Paths.- Cache-Aware and Cache-Oblivious Adaptive Sorting.- Simulated Annealing Beats Metropolis in Combinatorial Optimization.- On-line Algorithms.- Online Interval Coloring and Variants.- Dynamic Bin Packing of Unit Fractions Items.- Reordering Buffer Management for Non-uniform Cost Models.- Security Protocols Logic.- Combining Intruder Theories.- Computationally Sound Implementations of Equational Theories Against Passive Adversaries.- Password-Based Encryption Analyzed.- Random Graphs.- On the Cover Time of Random Geometric Graphs.- On the Existence of Hamiltonian Cycles in Random Intersection Graphs.- Optimal Cover Time for a Graph-Based Coupon Collector Process.- Stability and Similarity of Link Analysis Ranking Algorithms.- Concurrency I.- Up-to Techniques for Weak Bisimulation.- Petri Algebras.- A Finite Basis for Failure Semantics.- Spatial Logics for Bigraphs.- Encryption and related Primitives.- Completely Non-malleable Schemes.- Boneh-Franklin Identity Based Encryption Revisited.- Single-Database Private Information Retrieval with Constant Communication Rate.- Concurrent Zero Knowledge in the Public-Key Model.- Approximation Algorithms I.- A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines.- Polynomial Time Preemptive Sum-Multicoloring on Paths.- The Generalized Deadlock Resolution Problem.- Facility Location in Sublinear Time.- Games.- The Complexity of Stochastic Rabin and Streett Games.- Recursive Markov Decision Processes and Recursive Stochastic Games.- Decidability in Syntactic Control of Interference.- Idealized Algol with Ground Recursion, and DPDA Equivalence.- Approximation Algorithms II.- From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem.- How Well Can Primal-Dual and Local-Ratio Algorithms Perform?.- Approximating Max kCSP - Outperforming a Random Assignment with Almost a Linear Factor.- Lower Bounds.- On Dynamic Bit-Probe Complexity.- Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines.- Lower Bounds for Circuits with Few Modular and Symmetric Gates.- Probability.- Discrete Random Variables over Domains.- An Accessible Approach to Behavioural Pseudometrics.- Noisy Turing Machines.- Approximation Algorithms III.- A Better Approximation Ratio for the Vertex Cover Problem.- Stochastic Steiner Trees Without a Root.- Approximation Algorithms for the Max-coloring Problem.- Automata and Formal Languages II.- Tight Lower Bounds for Query Processing on Streaming and External Memory Data.- Decidability and Complexity Results for Timed Automata via Channel Machines.- Congruences for Visibly Pushdown Languages.- Approximation Algorithms IV.- Approximation Algorithms for Euclidean Group TSP.- Influential Nodes in a Diffusion Model for Social Networks.- An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks.- New Approaches for Virtual Private Network Design.- Algebraic Computation and Communication Complexity.- Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.- Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.- On the l-Ary GCD-Algorithm in Rings of Integers.- Concurrency II.- A Fully Abstract Encoding of the ?-Calculus with Data Terms.- Orthogonal Extensions in Structural Operational Semantics.- Basic Observables for a Calculus for Global Computing.- Compositional Verification of Asynchronous Processes via Constraint Solving.- String Matching and Computational Biology.- Optimal Spaced Seeds for Faster Approximate String Matching.- Fast Neighbor Joining.- Randomized Fast Design of Short DNA Words.- Quantum Complexity.- A Quantum Lower Bound for the Query Complexity of Simon's Problem.- All Quantum Adversary Methods Are Equivalent.- Quantum Complexity of Testing Group Commutativity.- Analysis and Verification.- Semantic-Based Code Obfuscation by Abstract Interpretation.- About Hoare Logics for Higher-Order Store.- The Polyranking Principle.- Geometry and Load Balancing.- Approximate Guarding of Monotone and Rectilinear Polygons.- Linear Time Algorithms for Clustering Problems in Any Dimensions.- Dynamic Diffusion Load Balancing.- Concrete Complexity and Codes.- On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group.- On the Hardness of Embeddings Between Two Finite Metrics.- Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval.- Model Theory and Model Checking.- Preservation Under Extensions on Well-Behaved Finite Structures.- Unsafe Grammars and Panic Automata.- Signaling P Systems and Verification Problems.