000 05816nam a22005775i 4500
001 978-3-540-46201-9
003 DE-He213
005 20160624102013.0
007 cr nn 008mamaa
008 121227s1989 gw | s |||| 0|eng d
020 _a9783540462019
_9978-3-540-46201-9
024 7 _a10.1007/BFb0035746
_2doi
050 4 _aQA8.9-QA10.3
072 7 _aUYA
_2bicssc
072 7 _aMAT018000
_2bisacsh
072 7 _aCOM051010
_2bisacsh
082 0 4 _a005.131
_223
245 1 0 _aAutomata, Languages and Programming
_h[electronic resource] :
_b16th International Colloquium Stresa, Italy, July 11–15, 1989 Proceedings /
_cedited by Giorgio Ausiello, Mariangiola Dezani-Ciancaglini, Simonetta Ronchi Rocca.
260 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c1989.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c1989.
300 _aXIV, 790 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,
_x0302-9743 ;
_v372
505 0 _aRealizable and unrealizable specifications of reactive systems -- Limitations of the upward separation technique (preliminary version) -- Lower bounds for the low hierarchy -- Efficient text searching of regular expressions -- Factors of words -- Asymptotically optimal distributed consensus -- Time lower bounds for CREW-PRAM computation of monotone functions -- Subduing self-application -- Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds -- Polymorphic rewriting conserves algebraic strong normalization and confluence -- Completion of finite codes with finite deciphering delay -- Relational semantics for recursive types and bounded quantification -- A singly-exponential stratification scheme for real semi-algebraic varieties and its applications -- About primitive recursive algorithms -- The definability of equational graphs in monadic second-order logic -- Dominoes and the regularity of DNA splicing languages -- Causal trees -- Infinite normal forms -- On recent trends in algebraic specification -- Automata with storage on infinite words -- Parallel algorithmic techniques for combinatorial computation -- On dice and coins: models of computation for random generation -- An optimal probabilistic algorithm for synchronous Byzantine agreement -- Finding triconnected components by local replacements -- An improved algorithm for approximate string matching -- A pointer-free data structure for merging heaps and min-max heaps -- Structured operational semantics and bisimulation as a congruence -- Parallel retrieval of scattered information -- Tensor rank is NP-complete -- The complexity of nonlinear separable optimization -- General methods for the analysis of the maximum size of dynamic data structures -- How to share concurrent asynchronous wait-free variables -- A new approach to formal language theory by kolmogorov complexity -- Dynamic algorithms in D.E. Knuth's model: A probabilistic analysis -- Completing the temporal picture -- Lower bounds for computations with the floor operation -- Programming, transforming, and proving with function abstractions and memories -- Automata theory meets circuit complexity -- Two versus one index register and modifiable versus non-modifiable programs -- Shortest paths without a map -- Modular system design applying graph grammars techniques -- Partial communations -- On the synthesis of an asynchronous reactive module -- The complexity of controlled selection -- Memory versus randomization in on-line algorithms -- Syntactic control of interference Part 2 -- Characteristic formulae -- A combinatorial technique for separating counting complexity classes -- Horn programs and semicomputable relations on abstract structures -- A note on model checking the modal v-calculus -- DI-domains as information systems.
520 _aThis volume contains the proceedings of ICALP 89, held at Stresa, Italy, July 11-15, 1989. ICALP 89 is the 16th International Colloquium on Automata, Languages and Programming in a series of meetings sponsored by the European Association for Theoretical Computer Science (EATCS). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata theory, formal language theory, analysis of algorithms, computational complexity, mathematical aspects of programming language definition, logic and semantics of programming languages, foundations of logic programming, theorem proving, software specification, computational geometry, data types and data structures, theory of data bases and knowledge based systems, cryptography, VLSI structures, parallel and distributed computing, models of concurrency and robotics.
650 0 _aComputer science.
650 0 _aComputer software.
650 0 _aLogic design.
650 0 _aCombinatorics.
650 1 4 _aComputer Science.
650 2 4 _aMathematical Logic and Formal Languages.
650 2 4 _aLogics and Meanings of Programs.
650 2 4 _aComputation by Abstract Devices.
650 2 4 _aAlgorithm Analysis and Problem Complexity.
650 2 4 _aCombinatorics.
650 2 4 _aProcessor Architectures.
700 1 _aAusiello, Giorgio.
_eeditor.
700 1 _aDezani-Ciancaglini, Mariangiola.
_eeditor.
700 1 _aRocca, Simonetta Ronchi.
_eeditor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783540513711
786 _dSpringer
830 0 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v372
856 4 0 _uhttp://dx.doi.org/10.1007/BFb0035746
942 _2EBK5732
_cEBK
999 _c35026
_d35026