FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science: 24th International Conference, Chennai, India, December 16-18, 2004. Proceedings

Max A. Alekseyev, Pavel A. Pevzner (auth.), Kamal Lodaya, Meena Mahajan (eds.)3540240586, 9783540240587, 9783540305385

This book constitutes the refereed proceedings of the 24th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2004, held in Chennai, India, in December 2004.

The 35 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 176 submissions. The papers address a broad variety of current issues in software science, programming theory, systems design and analysis, formal methods, mathematical logic, mathematical foundations, discrete mathematics, combinatorial mathematics, complexity theory, automata theory, and theoretical computer science in general.

---

Table of contents :
Front Matter….Pages –
Genome Halving Problem Revisited….Pages 1-15
Verifying Probabilistic Procedural Programs….Pages 16-31
Streaming Algorithms for Geometric Problems….Pages 32-34
Toward a Grainless Semantics for Shared-Variable Concurrency….Pages 35-48
Regular Languages, Unambiguous Concatenation and Computational Complexity….Pages 49-57
Decidability of Zenoness, Syntactic Boundedness and Token-Liveness for Dense-Timed Petri Nets….Pages 58-70
On the Urgency Expressiveness….Pages 71-83
Asynchronous Automata-Theoretic Characterization of Aperiodic Trace Languages….Pages 84-96
A Decidable Fragment of Separation Logic….Pages 97-109
Approximate Range Searching Using Binary Space Partitions….Pages 110-121
Representable Disjoint NP-Pairs….Pages 122-134
Symbolic Reachability Analysis of Higher-Order Context-Free Processes….Pages 135-147
Optimal Strategies in Priced Timed Game Automata….Pages 148-160
A Calculus for Trust Management….Pages 161-173
Short-Cuts on Star, Source and Planar Unfoldings….Pages 174-185
Subdividing Alpha Complex….Pages 186-197
Real-Counter Automata and Their Decision Problems….Pages 198-210
Adjunct Elimination Through Games in Static Ambient Logic….Pages 211-223
On the Bisimulation Invariant Fragment of Monadic Σ 1 in the Finite….Pages 224-236
On the Complexity of Hilbert’s 17th Problem….Pages 237-249
Who is Pointing When to Whom?….Pages 250-262
An Almost Linear Time Approximation Algorithm for the Permanent of a Random (0-1) Matrix….Pages 263-274
Distributed Games with Causal Memory Are Decidable for Series-Parallel Systems….Pages 275-286
Expand, Enlarge, and Check: New Algorithms for the Coverability Problem of WSTS….Pages 287-298
Minimum Weight Pseudo-Triangulations….Pages 299-310
Join Algorithms for the Theory of Uninterpreted Functions….Pages 311-323
No, Coreset, No Cry….Pages 324-335
Hardness Hypotheses, Derandomization, and Circuit Complexity….Pages 336-347
Improved Approximation Algorithms for Maximum Graph Partitioning Problems Extended Abstract….Pages 348-359
Learning Languages from Positive Data and a Finite Number of Queries….Pages 360-371
The Complexity of the Local Hamiltonian Problem….Pages 372-383
Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds….Pages 384-395
Adaptive Stabilization of Reactive Protocols….Pages 396-407
Visibly Pushdown Games….Pages 408-420
Refinement and Separation Contexts….Pages 421-433
Decidability of MSO Theories of Tree Structures….Pages 434-446
Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks….Pages 447-459
Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching Require Exponential Size….Pages 460-468
Testing Geometric Convexity….Pages 469-480
Complexity of Linear Connectivity Problems in Directed Hypergraphs….Pages 481-493
Actively Learning to Verify Safety for FIFO Automata….Pages 494-505
Reasoning About Game Equilibria Using Temporal Logic….Pages 506-517
Alternation in Equational Tree Automata Modulo XOR….Pages 518-530
Back Matter….Pages –