000 07677nam a22006855i 4500
001 978-3-540-70583-3
003 DE-He213
005 20240730173337.0
007 cr nn 008mamaa
008 100301s2008 gw | s |||| 0|eng d
020 _a9783540705833
_9978-3-540-70583-3
024 7 _a10.1007/978-3-540-70583-3
_2doi
050 4 _aQA76.758
072 7 _aUMZ
_2bicssc
072 7 _aCOM051230
_2bisacsh
072 7 _aUMZ
_2thema
082 0 4 _a005.1
_223
245 1 0 _aAutomata, Languages and Programming
_h[electronic resource] :
_b35th International Colloquium, ICALP 2008 Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II /
_cedited by Luca Aceto, Ivan Damgaard, Leslie Ann Goldberg, Magnus M. Halldorsson, Anna Ingolfsdottir, Igor Walukiewicz.
250 _a1st ed. 2008.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2008.
300 _aXXII, 734 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5126
505 0 _aInvited Lectures -- Composable Formal Security Analysis: Juggling Soundness, Simplicity and Efficiency -- Newton's Method for ?-Continuous Semirings -- Track B: Logic, Semantics, and Theory of Programming -- The Tractability Frontier for NFA Minimization -- Finite Automata, Digraph Connectivity, and Regular Expression Size -- Leftist Grammars Are Non-primitive Recursive -- On the Computational Completeness of Equations over Sets of Natural Numbers -- Placement Inference for a Client-Server Calculus -- Extended pi-Calculi -- Completeness and Logical Full Abstraction in Modal Logics for Typed Mobile Processes -- On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases -- On Expressiveness and Complexity in Real-Time Model Checking -- STORMED Hybrid Systems -- Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives -- On Datalog vs. LFP -- Directed st-Connectivity Is Not Expressible in Symmetric Datalog -- Non-dichotomies in Constraint Satisfaction Complexity -- Quantified Constraint Satisfaction and the Polynomially Generated Powers Property -- When Does Partial Commutative Closure Preserve Regularity? -- Weighted Logics for Nested Words and Algebraic Formal Power Series -- Tree Languages Defined in First-Order Logic with One Quantifier Alternation -- Duality and Equational Theory of Regular Languages -- Reversible Flowchart Languages and the Structured Reversible Program Theorem -- Attribute Grammars and Categorical Semantics -- A Domain Theoretic Model of Qubit Channels -- Interacting Quantum Observables -- Perpetuality for Full and Safe Composition (in a Constructive Setting) -- A System F with Call-by-Name Exceptions -- Linear Logical Algorithms -- A Simple Model of Separation Logic for Higher-Order Store -- OpenImplication -- ATL* Satisfiability Is 2EXPTIME-Complete -- Visibly Pushdown Transducers -- The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata -- Analyzing Context-Free Grammars Using an Incremental SAT Solver -- Track C: Security and Cryptography Foundations -- Weak Pseudorandom Functions in Minicrypt -- On Black-Box Ring Extraction and Integer Factorization -- Extractable Perfectly One-Way Functions -- Error-Tolerant Combiners for Oblivious Primitives -- Asynchronous Multi-Party Computation with Quadratic Communication -- Improved Garbled Circuit: Free XOR Gates and Applications -- Improving the Round Complexity of VSS in Point-to-Point Networks -- How to Protect Yourself without Perfect Shredding -- Universally Composable Undeniable Signature -- Interactive PCP -- Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model -- Delegating Capabilities in Predicate Encryption Systems -- Bounded Ciphertext Policy Attribute Based Encryption -- Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks -- Composable Security in the Bounded-Quantum-Storage Model -- On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak -- History-Independent Cuckoo Hashing -- Building a Collision-Resistant Compression Function from Non-compressing Primitives -- Robust Multi-property Combiners for Hash Functions Revisited -- Homomorphic Encryption with CCA Security -- How to Encrypt with the LPN Problem -- Could SFLASH be Repaired? -- Password Mistyping in Two-Factor-Authenticated Key Exchange -- Affiliation-Hiding Envelope and Authentication Schemes with Efficient Support for Multiple Credentials.
520 _aThe two-volume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008. The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5126 contains 56 contributions of track B and track C selected from 208 submissions and 2 invited lectures. The papers for track B are organized in topical sections on bounds, distributed computation, real-time and probabilistic systems, logic and complexity, words and trees, nonstandard models of computation, reasoning about computation, and verification. The papers of track C cover topics in security and cryptography such as theory, secure computation, two-party protocols and zero-knowledge, encryption with special properties/quantum cryptography, various types of hashing, as well as public-key cryptography and authentication.
650 0 _aSoftware engineering.
_94138
650 0 _aComputer programming.
_94169
650 0 _aComputer science.
_99832
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aDiscrete mathematics.
_912873
650 0 _aNumerical analysis.
_94603
650 0 _aArtificial intelligence
_xData processing.
_921787
650 1 4 _aSoftware Engineering.
_94138
650 2 4 _aProgramming Techniques.
_9107983
650 2 4 _aTheory of Computation.
_9107984
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
650 2 4 _aNumerical Analysis.
_94603
650 2 4 _aData Science.
_934092
700 1 _aAceto, Luca.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9107985
700 1 _aDamgaard, Ivan.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9107986
700 1 _aGoldberg, Leslie Ann.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9107987
700 1 _aHalldorsson, Magnus M.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9107988
700 1 _aIngolfsdottir, Anna.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9107989
700 1 _aWalukiewicz, Igor.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9107990
710 2 _aSpringerLink (Online service)
_9107991
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540705826
776 0 8 _iPrinted edition:
_z9783540866640
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5126
_9107992
856 4 0 _uhttps://doi.org/10.1007/978-3-540-70583-3
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c88879
_d88879