FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

Inhaltsverzeichnis

• Invited Papers.
• Genome Halving Problem Revisited.
• Verifying Probabilistic Procedural Programs.
• Streaming Algorithms for Geometric Problems.
• Toward a Grainless Semantics for Shared-Variable Concurrency.
• Regular Languages, Unambiguous Concatenation and Computational Complexity.
• Contributed Papers.
• Decidability of Zenoness, Syntactic Boundedness and Token-Liveness for Dense-Timed Petri Nets.
• On the Urgency Expressiveness.
• Asynchronous Automata-Theoretic Characterization of Aperiodic Trace Languages.
• A Decidable Fragment of Separation Logic.
• Approximate Range Searching Using Binary Space Partitions.
• Representable Disjoint NP-Pairs.
• Symbolic Reachability Analysis of Higher-Order Context-Free Processes.
• Optimal Strategies in Priced Timed Game Automata.
• A Calculus for Trust Management.
• Short-Cuts on Star, Source and Planar Unfoldings.
• Subdividing Alpha Complex.
• Real-Counter Automata and Their Decision Problems.
• Adjunct Elimination Through Games in Static Ambient Logic.
• On the Bisimulation Invariant Fragment of Monadic ?1 in the Finite.
• On the Complexity of Hilbert’s 17th Problem.
• Who is Pointing When to Whom?.
• An Almost Linear Time Approximation Algorithm for the Permanent of a Random (0-1) Matrix.
• Distributed Games with Causal Memory Are Decidable for Series-Parallel Systems.
• Expand, Enlarge, and Check: New Algorithms for the Coverability Problem of WSTS.
• Minimum Weight Pseudo-Triangulations.
• Join Algorithms for the Theory of Uninterpreted Functions.
• No, Coreset, No Cry.
• Hardness Hypotheses, Derandomization, and Circuit Complexity.
• Improved Approximation Algorithms for Maximum Graph Partitioning Problems Extended Abstract.
• Learning Languages from Positive Data and a Finite Number of Queries.
• The Complexity of the Local Hamiltonian Problem.
• Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds.
• Adaptive Stabilization of Reactive Protocols.
• Visibly Pushdown Games.
• Refinement and Separation Contexts.
• Decidability of MSO Theories of Tree Structures.
• Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks.
• Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching Require Exponential Size.
• Testing Geometric Convexity.
• Complexity of Linear Connectivity Problems in Directed Hypergraphs.
• Actively Learning to Verify Safety for FIFO Automata.
• Reasoning About Game Equilibria Using Temporal Logic.
• Alternation in Equational Tree Automata Modulo XOR.