LEADER 06922nam 22008175 450 001 996465672703316 005 20200703033258.0 010 $a3-540-45294-X 024 7 $a10.1007/3-540-45294-X 035 $a(CKB)1000000000211649 035 $a(SSID)ssj0000323333 035 $a(PQKBManifestationID)11244537 035 $a(PQKBTitleCode)TC0000323333 035 $a(PQKBWorkID)10299395 035 $a(PQKB)11599417 035 $a(DE-He213)978-3-540-45294-2 035 $a(MiAaPQ)EBC3072900 035 $a(PPN)155231553 035 $a(EXLCZ)991000000000211649 100 $a20121227d2001 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aFST TCS 2001: Foundations of Software Technology and Theoretical Computer Science$b[electronic resource] $e21st Conference, Bangalore, India, December 13-15, 2001, Proceedings /$fedited by Ramesh Hariharan, Madhavan Mukund, V. Vinay 205 $a1st ed. 2001. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2001. 215 $a1 online resource (XII, 352 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v2245 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-43002-4 320 $aIncludes bibliographical references at the end of each chapters and index. 327 $aInvited Papers -- When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity -- Approximation Schemes for Geometric NP-Hard Problems: A Survey -- On Clustering Using Random Walks -- An Introduction to Decidability of DPDA Equivalence -- Semidefinite Programming Based Approximation Algorithms -- Contributed Papers -- Hard Sets and Pseudo-random Generators for Constant Depth Circuits -- The First-Order Isomorphism Theorem -- Thresholds and Optimal Binary Comparison Search Trees -- Distributed LTL Model Checking Based on Negative Cycle Detection -- Computability and Complexity Results for a Spatial Assertion Language for Data Structures -- Using Nondeterminism to Design Efficient Deterministic Algorithms -- Liveness Verification of Reversal-Bounded Multicounter Machines with a Free Counter -- A Mechanically Verified Compiling Specification for a Lisp Compiler -- Beyond Regular Model Checking -- Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity -- Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel -- List Decoding from Erasures: Bounds and Code Constructions -- Verification of a Leader Election Algorithm in Timed Asynchronous Systems -- Efficient Addition on Field Programmable Gate Arrays -- The Directed Minimum-Degree Spanning Tree Problem -- I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems -- Beyond Message Sequence Graphs -- Grouping Techniques for One Machine Scheduling Subject to Precedence Constraints -- Properties of Distributed Timed-Arc Petri Nets -- From Falsification to Verification -- On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems -- Range Allocation for Equivalence Logic -- Rewrite Closure for Ground and Cancellative AC Theories. 330 $aThis volume contains the proceedings of the 21st international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2001), organized under the auspices of the Indian Association for Research in Computing Science (IARCS). This year?s conference attracted 73 submissions from 20 countries. Each s- mission was reviewed by at least three independent referees. In a departure from previous conferences, the ?nal selection of the papers making up the program was done through an electronic discussion spanning two weeks, without a physical meeting of the Program Committee (PC). Since the PC of FSTTCS is distributed across the globe, it is very di?cult to ?x a meeting whose time and venue is convenient for a substantial fraction of the PC. Given this, it was felt that an electronic discussion would enable all members to participate on a more equal footing in the ?nal selection. All reviews, scores, and comments were posted on a secure website, with a mechanism for making updates and automatically sending noti?cations by email to relevant members of the PC. All PC members participated actively in the discussion. The general feedback on the arrangement was very positive, so we hope to continue this in future years. We had ?ve invited speakers this year: Eric Allender, Sanjeev Arora, David Harel, Colin Stirling, and Uri Zwick. We thank them for having readily accepted our invitation to talk at the conference and for providing abstracts (and even full papers) for the proceedings. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v2245 606 $aComputers 606 $aSoftware engineering 606 $aApplication software 606 $aComputer logic 606 $aProgramming languages (Electronic computers) 606 $aMathematical logic 606 $aTheory of Computation$3https://scigraph.springernature.com/ontologies/product-market-codes/I16005 606 $aSoftware Engineering/Programming and Operating Systems$3https://scigraph.springernature.com/ontologies/product-market-codes/I14002 606 $aComputer Applications$3https://scigraph.springernature.com/ontologies/product-market-codes/I23001 606 $aLogics and Meanings of Programs$3https://scigraph.springernature.com/ontologies/product-market-codes/I1603X 606 $aProgramming Languages, Compilers, Interpreters$3https://scigraph.springernature.com/ontologies/product-market-codes/I14037 606 $aMathematical Logic and Formal Languages$3https://scigraph.springernature.com/ontologies/product-market-codes/I16048 615 0$aComputers. 615 0$aSoftware engineering. 615 0$aApplication software. 615 0$aComputer logic. 615 0$aProgramming languages (Electronic computers). 615 0$aMathematical logic. 615 14$aTheory of Computation. 615 24$aSoftware Engineering/Programming and Operating Systems. 615 24$aComputer Applications. 615 24$aLogics and Meanings of Programs. 615 24$aProgramming Languages, Compilers, Interpreters. 615 24$aMathematical Logic and Formal Languages. 676 $a005.1 702 $aHariharan$b Ramesh$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aMukund$b Madhavan$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aVinay$b V$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996465672703316 996 $aFST TCS 2001: Foundations of Software Technology and Theoretical Computer Science$91980347 997 $aUNISA