000 05841nam a22006375i 4500
001 978-3-540-45294-2
003 DE-He213
005 20240423132527.0
007 cr nn 008mamaa
008 121227s2001 gw | s |||| 0|eng d
020 _a9783540452942
_9978-3-540-45294-2
024 7 _a10.1007/3-540-45294-X
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
245 1 0 _aFST TCS 2001: Foundations of Software Technology and Theoretical Computer Science
_h[electronic resource] :
_b21st Conference, Bangalore, India, December 13-15, 2001, Proceedings /
_cedited by Ramesh Hariharan, Madhavan Mukund, V. Vinay.
250 _a1st ed. 2001.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2001.
300 _aXII, 352 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x1611-3349 ;
_v2245
505 0 _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.
520 _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.
650 0 _aComputer science.
650 0 _aSoftware engineering.
650 0 _aApplication software.
650 0 _aCompilers (Computer programs).
650 0 _aMachine theory.
650 1 4 _aTheory of Computation.
650 2 4 _aSoftware Engineering.
650 2 4 _aComputer and Information Systems Applications.
650 2 4 _aComputer Science Logic and Foundations of Programming.
650 2 4 _aCompilers and Interpreters.
650 2 4 _aFormal Languages and Automata Theory.
700 1 _aHariharan, Ramesh.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aMukund, Madhavan.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aVinay, V.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540430025
776 0 8 _iPrinted edition:
_z9783662205396
830 0 _aLecture Notes in Computer Science,
_x1611-3349 ;
_v2245
856 4 0 _uhttps://doi.org/10.1007/3-540-45294-X
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
912 _aZDB-2-BAE
942 _cSPRINGER
999 _c188742
_d188742