By Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Paul Spirakis (auth.), Carlo Blundo, Cosimo Laneve (eds.)

This e-book constitutes the refereed court cases of the eighth Italian convention on Theoretical desktop technology, ICTCS 2003, held in Bertinoro, Italy in October 2003.

The 27 revised complete papers provided including an invited paper and abstracts of two invited talks have been rigorously reviewed and chosen from sixty five submissions. The papers are prepared in topical sections on application design-models and research, algorithms and complexity, semantics and formal languages, and protection and cryptography.

Show description

Read or Download Theoretical Computer Science: 8th Italian Conference, ICTCS 2003, Bertinoro, Italy, October 13-15, 2003. Proceedings PDF

Best italian books

Bossic instinct

Il libro raccoglie le principali vignette edite ed inedite del 1993. Un anno così burrascoso dal punto di vista politico da rappresentare, in step with Forattini, un'autentica cuccagna.

Additional info for Theoretical Computer Science: 8th Italian Conference, ICTCS 2003, Bertinoro, Italy, October 13-15, 2003. Proceedings

Sample text

Vetta, “Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions,” Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, October 2002, pp. 416–425. Certification of Memory Usage Martin Hofmann Institut f¨ ur Informatik Ludwig-Maximilians-Universit¨ at M¨ unchen Oettingenstrasse 67 D-80538 M¨ unchen, Germany Abstract. We describe a type-based approach for inferring heap space usage of certain functional programs and a mechanism for generating certificates as to the thus inferred memory consumption in the form of proofs in a VDM-style program logic fore Java bytecode (Java bytecode being the target of compilation).

Note that every generic term is a linear λ-term. e. duplication) is used only in data. Due to this restriction, simulation of Turing machines is more sophisticated than before. Let M and δ be as before. (B −◦ α −◦ α) −◦ ((α −◦ α)k ⊗ A). Then each term of type IDk [A] encodes k words as well as an element of type A. (c0 ◦ c1 ◦ c0) ⊗ (c1 ◦ c1) ⊗ q : ID2 [Bn ]. Lemma 7 (Decomposition). For every k ≥ 1, there exists a generic term dec of type IDk [Bn ] −◦ ID2k [B ⊗ Bn ] such that for any i1 w1 , . .

Formally, let cntr3 : B −◦ B3 be a generalized contraction which produces three copies of a given boolean value, and define G(m, w1 , w2 , i2 , s, c1 , c2 ) to be let cntr3 (m) be m1 ⊗ m2 ⊗ m3 in (let m1 si2 be j1 ⊗ j2 in (let m2 w1 w2 be v1 ⊗ v2 in m3 v1 (c1 j1 ◦ c2 j2 (v2 )))), which is of type m : B, w1 : α, w2 : α, i2 : B, s : B, c1 : B −◦ α −◦ α, c2 : B −◦ α −◦ α G(m, w1 , w2 , i2 , s, c1 , c2 ) : α ⊗ α. Then, depending on the value of m, we have G(true, w1 , w2 , i2 , s, c, c) −→∗ w1 ⊗ (cs ◦ ci2 (w2 )); G(false, w1 , w2 , i2 , s, c, c) −→∗ (ci2 ◦ cs(w1 )) ⊗ w2 .

Download PDF sample

Rated 4.87 of 5 – based on 34 votes