FST TCS 2000: Foundations of Software Technology and Theoretical Science: 20th Conference, New Delhi, India, December13-15, 2000 Proceedings (Lecture Notes in Computer Science, 1974)

ISBN 10: 3540414134 / ISBN 13: 9783540414131

Editore: Springer, 2000

Riguardo questo articolo

In. Codice articolo ria9783540414131_new

Dati bibliografici

Titolo: FST TCS 2000: Foundations of Software ...

Casa editrice: Springer

Data di pubblicazione: 2000

Legatura: Brossura

Condizione: New

Descrizione articolo

Riassunto:

The Foundations of SoftwareTechnology and Theoretical Computer Science c- ference (FST TCS) is a well-established annual event in the theoretical computer science community. The conference provides a forum for researchers to present interesting new results in several areas of theoretical computer science. The c- ference is now in its twentieth year and has continued to attract high-quality submissions and reputed invited speakers. This year sconference attracted 141 submissions(of which 5 werewithdrawn) from over 25 countries. Each submission was reviewed by at least three referees, with most receiving more than four reviews. The Program Committee met in New Delhi on 5 and 6 August 2000, with many members participating electr- ically over the Internet. The discussions continued over the Internet for several days and we ?nally selected 36 papers for presentation at the conference and inclusion in the proceedings. We thank the Program Committee for their - perlative e?orts in ?nding top quality reviewers and working extremely hard to ensure the quality of the conference. We also thank all our reviewers for prov- ing detailed and informative feedback about the papers. Rich Gerber s START program greatly simpli?ed managing the submissions and the PC work. Wearegratefulto oursixinvited speakers,PeterBuneman,BernardChazelle, Allen Emerson, Martin Gr¨ otschel, Jos´ e Meseguer, and Philip Wadler for agr- ing to speak at the conference and for providing written contributions that are included in the proceedings. With the main conference this year, there are two satellite workshops on RecentAdvancesinProgrammingLanguages and onComputationalGeometry.

Contenuti:

Invited Presentations.- Model Checking: Theory into Practice.- An Algebra for XML Query.- Irregularities of Distribution, Derandomization, and Complexity Theory.- Rewriting Logic as a Metalogical Framework.- Frequency Assignment in Mobile Phone Systems.- Data Provenance: Some Basic Issues.- Contributions.- Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition.- On-Line Edge-Coloring with a Fixed Number of Colors.- On Approximability of the Independent/Connected Edge Dominating Set Problems.- Model Checking CTL Properties of Pushdown Systems.- A Decidable Dense Branching-Time Temporal Logic.- Fair Equivalence Relations.- Arithmetic Circuits and Polynomial Replacement Systems.- Depth-3 Arithmetic Circuits for S inn su2 (X) and Extensions of the Graham-Pollack Theorem.- The Bounded Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs Is Infinite.- Combining Semantics with Non-standard Interpreter Hierarchies.- Using Modes to Ensure Subject Reduction for Typed Logic Programs with Subtyping.- Dynamically Ordered Probabilistic Choice Logic Programming.- Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems.- Planar Graph Blocking for External Searching.- A Complete Fragment of Higher-Order Duration ?-Calculus.- A Complete Axiomatisation for Timed Automata.- Text Sparsification via Local Maxima.- Approximate Swapped Matching.- A Semantic Theory for Heterogeneous System Design.- Formal Verification of the Ricart-Agrawala Algorithm.- On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation.- ? in2 sup -Completeness: A Classical Approach for New Results.- Is the Standard Proof System for SAT P-Optimal?.- A General Framework for Types in Graph Rewriting.- The Ground Congruence for Chi Calculus.- Inheritance in the Join Calculus.- Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints.- Dynamic Spectrum Allocation: The Impotency of Duration Notification.- The Fine Structure of Game Lambda Models.- Strong Normalization of Second Order Symmetric ?-Calculus.- Scheduling to Minimize the Average Completion Time of Dedicated Tasks.- Hunting for Functionally Analogous Genes.- Keeping Track of the Latest Gossip in Shared Memory Systems.- Concurrent Knowledge and Logical Clock Abstractions.- Decidable Hierarchies of Starfree Languages.- Prefix Languages of Church-Rosser Languages.