Theoretical Computer Science

by Degano, Pierpaolo; Vaccaro, Ugo; Pirillo, Giuseppe

• ISBN13: 9789810236557
• ISBN10: 9810236557
• Format: Hardcover
• Copyright: 1998-09-01
• Publisher: World Scientific Pub Co Inc

Summary

The Italian Conference on Theoretical Computer Science (ICTCS '98) is the annual conference of the Italian Chapter of the European Association for Theoretical Computer Science. The Conference aims at enabling computer scientists, especially young researchers to enter the community and to exchange theoretical ideas and results, as well as theoretical based practical experiences and tools in computer science.

Table of Contents

Bohm's Theorem for Bohm's Trees (Invited Talk)	1	(23)
M. Dezani-Ciancaglini
B. Intrigila
M. Venturini-Zilli
Concrete Syntax for Intuitionistic Light Affine Logic with Polymorphic Type Assignment	24	(13)
L. Roversi
A Type Assignment System for the Game Semantics	37	(11)
P. Di Gianantonio
G. Franco
A Game Semantics Foundation for Logic Programming	48	(4)
R. Di Cosmo
J.-V. Loddo
S. Nicolet
Tight Bounds on Broadcasting with Dynamic Faults	52	(13)
G. De Marco
A. A. Rescigno
A New Modular Division Algorithm and Applications	65	(12)
M. S. Sedjelmaci
C. Lavault
Fast Single Precision Evaluation of Sign of Determinants	77	(13)
F. d'Amore
P. G. Franciosa
From Bandwidth k to Pathwidth k	90	(12)
A. Proskurowski
J. A. Telle
Maintaining dynamic graph properties deterministically	102	(12)
M. Marzolla
Rooted Spanning Trees with Small Weight and Average Length	114	(12)
G. Frederickson
R. Solis-Oba
A Symbolic Semantics for Abstract Model Checking	126	(3)
F. Levi
A Fixpoint-Based Axiom System for ACTL	129	(12)
G. Lenzi
Proof Systems with Cut Elimination for MTL≤	141	(12)
F. Montagna
G. M. Pinna
E. B. P. Tiezzi
A Natural Deduction Style Proof System for Propositional μ-Calculus and its Formalization in Inductive Type Theories	153	(13)
M. Miculan
Ambient Decor (Invited Talk)	166	(2)
L. Cardelli
A. D. Gordon
Implementing Tile Systems: some Examples from Process Calculi	168	(12)
R. Bruni
J. Meseguer
U. Montanari
Some Concurrency Models in a Categorical Framework	180	(12)
C. Bodei
Enabling and General Distributions in Stochastic Process Algebras	192	(12)
C. Priami
Functional and Performance Modeling and Analysis of Token Ring using EMPA	204	(12)
M. Bernardo
M. Bravetti
Threshold Circuits for some Matrix Operations. Consequences on Regular and Probabilistic Languages	216	(12)
C. Mereghetti
B. Palano
Q---ary Searching with Lies	228	(13)
F. Cicalese
Quantum NP is Hard for PH	241	(12)
S. Fenner
F. Green
S. Homer
R. Pruim
Downward Collapse from a Weaker Hypothesis	253	(12)
E. Hemaspaandra
L. A. Hemaspaandra
H. Hempel
On the Polynomial Representation of Boolean Functions over GF(2)	265	(12)
A. Bernasconi
Spectral Techniques for Depth-3 Threshold Circuits	277	(13)
G. Cattaneo
A. Leporati
G. Mauri
New Constructions for Visual Cryptography	290	(14)
C. Blundo
A. De Bonis
Languages for Description and Analysis of Authentication Protocols	304	(12)
F. Martinelli
Using Entity Locations for the Analysis of Authentication Protocols	316	(12)
R. Focardi
Analysis of Normal Logic Programs	328	(3)
F. Fages
R. Gori
An Experiment in Domain Refinement: Type Domains and Type Representations for Logic Programs	331	(4)
F. Spoto
Call-Correct Specialisation of Logic Programs	335	(12)
A. Bossi
S. Rossi
Factorizing Codes and Krasner Factorizations	347	(12)
C. De Felice
R. Zizza
Transition Diagram System and Normal Form Algorithms	359	(12)
D. Giammarresi
D. Wood
On the Extension of Fine and Wilf's Periodicity Theorem to Linear Automata	371	(13)
G. Melideo
C. Pasquarelli
S. Varricchio
Author Index	384