Search

Your search keyword '"Dal Lago, Ugo"' showing total 431 results
Start Over Author "Dal Lago, Ugo"

Refine your results

more »

more »

more »

more »
431 results on '"Dal Lago, Ugo"'

1. On Basic Feasible Functionals and the Interpretation Method

Author

Baillot, Patrick, Dal Lago, Ugo, Kop, Cynthia, Vale, Deivid, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kobayashi, Naoki, editor, and Worrell, James, editor

Published
2024
Full Text
View/download PDF

6. On Measure Quantifiers in First-Order Arithmetic

Author

Antonelli, Melissa, Dal Lago, Ugo, Pistone, Paolo, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, De Mol, Liesbeth, editor, Weiermann, Andreas, editor, Manea, Florin, editor, and Fernández-Duque, David, editor

Published
2021
Full Text
View/download PDF

7. Decomposing Probabilistic Lambda-Calculi

Author

Dal Lago, Ugo, Guerrieri, Giulio, Heijltjes, Willem, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Goubault-Larrecq, Jean, editor, and König, Barbara, editor

Published
2020
Full Text
View/download PDF

8. Effectful Normal Form Bisimulation

Author

Dal Lago, Ugo, Gavazzo, Francesco, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, and Caires, Luís, editor

Published
2019
Full Text
View/download PDF

11. On Probabilistic Term Rewriting

Author

Avanzini, Martin, Dal Lago, Ugo, Yamada, Akihisa, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Gallagher, John P., editor, and Sulzmann, Martin, editor

Published
2018
Full Text
View/download PDF

13. On Higher-Order Probabilistic Subrecursion

Author

Breuvart, Flavien, Dal Lago, Ugo, Herrou, Agathe, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Esparza, Javier, editor, and Murawski, Andrzej S., editor

Published
2017
Full Text
View/download PDF

14. Probabilistic Termination by Monadic Affine Sized Typing

Author

Dal Lago, Ugo, Grellois, Charles, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Yang, Hongseok, editor

Published
2017
Full Text
View/download PDF

15. Metric Reasoning About -Terms: The General Case

Author

Crubillé, Raphaëlle, Dal Lago, Ugo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Yang, Hongseok, editor

Published
2017
Full Text
View/download PDF

18. Foundations of Software Science and Computation Structures : 21st International Conference, FOSSACS 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14–20, 2018. Proceedings

Author

Baier, Christel and Dal Lago, Ugo

Subjects
Computers / Artificial Intelligence
Abstract

This book constitutes the proceedings of the 21st International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2018, which took place in Thessaloniki, Greece, in April 2018, held as part of the European Joint Conference on Theory and Practice of Software, ETAPS 2018.The 31 papers presented in this volume were carefully reviewed and selected from 103 submissions. The papers are organized in topical sections named: semantics; linearity; concurrency; lambda-calculi and types; category theory and quantum control; quantitative models; logics and equational theories; and graphs and automata.

Published
2018

20. Applicative Bisimulation and Quantum λ-Calculi

Author

Dal Lago, Ugo, Rioli, Alessandro, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dastani, Mehdi, editor, and Sirjani, Marjan, editor

Published
2015
Full Text
View/download PDF

21. On Applicative Similarity, Sequentiality, and Full Abstraction

Author

Crubillé, Raphaëlle, Dal Lago, Ugo, Sangiorgi, Davide, Vignudelli, Valeria, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Meyer, Roland, editor, Platzer, André, editor, and Wehrheim, Heike, editor

Published
2015
Full Text
View/download PDF

22. On Equivalences, Metrics, and Polynomial Time

Author

Cappai, Alberto, Dal Lago, Ugo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kosowski, Adrian, editor, and Walukiewicz, Igor, editor

Published
2015
Full Text
View/download PDF

23. On Dynamic Lifting and Effect Typing in Circuit Description Languages

Author

Colledan, Andrea, Dal Lago, Ugo, Colledan, Andrea, and Dal Lago, Ugo

Abstract

In the realm of quantum computing, circuit description languages represent a valid alternative to traditional QRAM-style languages. They indeed allow for finer control over the output circuit, without sacrificing flexibility nor modularity. We introduce a generalization of the paradigmatic lambda-calculus Proto-Quipper-M, which models the core features of the quantum circuit description language Quipper. The extension, called Proto-Quipper-K, is meant to capture a very general form of dynamic lifting. This is made possible by the introduction of a rich type and effect system in which not only computations, but also the very types are effectful. The main results we give for the introduced language are the classic type soundness results, namely subject reduction and progress.

Published
2023
Full Text
View/download PDF

24. Towards a logical foundation of randomized computation

Author

Dal Lago, Ugo, Antonelli, Melissa <1993>, Dal Lago, Ugo, and Antonelli, Melissa <1993>

Abstract

This dissertation investigates the relations between logic and TCS in the probabilistic setting. It is motivated by two main considerations. On the one hand, since their appearance in the 1960s-1970s, probabilistic models have become increasingly pervasive in several fast-growing areas of CS. On the other, the study and development of (deterministic) computational models has considerably benefitted from the mutual interchanges between logic and CS. Nevertheless, probabilistic computation was only marginally touched by such fruitful interactions. The goal of this thesis is precisely to (start) bring(ing) this gap, by developing logical systems corresponding to specific aspects of randomized computation and, therefore, by generalizing standard achievements to the probabilistic realm. To do so, our key ingredient is the introduction of new, measure-sensitive quantifiers associated with quantitative interpretations. The dissertation is tripartite. In the first part, we focus on the relation between logic and counting complexity classes. We show that, due to our classical counting propositional logic, it is possible to generalize to counting classes, the standard results by Cook and Meyer and Stockmeyer linking propositional logic and the polynomial hierarchy. Indeed, we show that the validity problem for counting-quantified formulae captures the corresponding level in Wagner's hierarchy. In the second part, we consider programming language theory. Type systems for randomized \lambda-calculi, also guaranteeing various forms of termination properties, were introduced in the last decades, but these are not "logically oriented" and no Curry-Howard correspondence is known for them. Following intuitions coming from counting logics, we define the first probabilistic version of the correspondence. Finally, we consider the relationship between arithmetic and computation. We present a quantitative extension of the language of arithmetic able to formalize basic results from probab

Published
2023

25. On the Lattice of Program Metrics

Author

Ugo Dal Lago and Naohiko Hoshino and Paolo Pistone, Dal Lago, Ugo, Hoshino, Naohiko, Pistone, Paolo, Ugo Dal Lago and Naohiko Hoshino and Paolo Pistone, Dal Lago, Ugo, Hoshino, Naohiko, and Pistone, Paolo

Abstract

In this paper we are concerned with understanding the nature of program metrics for calculi with higher-order types, seen as natural generalizations of program equivalences. Some of the metrics we are interested in are well-known, such as those based on the interpretation of terms in metric spaces and those obtained by generalizing observational equivalence. We also introduce a new one, called the interactive metric, built by applying the well-known Int-Construction to the category of metric complete partial orders. Our aim is then to understand how these metrics relate to each other, i.e., whether and in which cases one such metric refines another, in analogy with corresponding well-studied problems about program equivalences. The results we obtain are twofold. We first show that the metrics of semantic origin, i.e., the denotational and interactive ones, lie in between the observational and equational metrics and that in some cases, these inclusions are strict. Then, we give a result about the relationship between the denotational and interactive metrics, revealing that the former is less discriminating than the latter. All our results are given for a linear lambda-calculus, and some of them can be generalized to calculi with graded comonads, in the style of Fuzz.

Published
2023
Full Text
View/download PDF

26. Contextual Behavioural Metrics

Author

Ugo Dal Lago and Maurizio Murgia, Dal Lago, Ugo, Murgia, Maurizio, Ugo Dal Lago and Maurizio Murgia, Dal Lago, Ugo, and Murgia, Maurizio

Abstract

We introduce contextual behavioural metrics (CBMs) as a novel way of measuring the discrepancy in behaviour between processes, taking into account both quantitative aspects and contextual information. This way, process distances by construction take the environment into account: two (non-equivalent) processes may still exhibit very similar behaviour in some contexts, e.g., when certain actions are never performed. We first show how CBMs capture many well-known notions of equivalence and metric, including Larsen’s environmental parametrized bisimulation. We then study compositional properties of CBMs with respect to some common process algebraic operators, namely prefixing, restriction, non-deterministic sum, parallel composition and replication.

Published
2023
Full Text
View/download PDF

27. Open Higher-Order Logic

Author

Ugo Dal Lago and Francesco Gavazzo and Alexis Ghyselen, Dal Lago, Ugo, Gavazzo, Francesco, Ghyselen, Alexis, Ugo Dal Lago and Francesco Gavazzo and Alexis Ghyselen, Dal Lago, Ugo, Gavazzo, Francesco, and Ghyselen, Alexis

Abstract

We introduce a variation on Barthe et al.’s higher-order logic in which formulas are interpreted as predicates over open rather than closed objects. This way, concepts which have an intrinsically functional nature, like continuity, differentiability, or monotonicity, can be expressed and reasoned about in a very natural way, following the structure of the underlying program. We give open higher-order logic in distinct flavors, and in particular in its relational and local versions, the latter being tailored for situations in which properties hold only in part of the underlying function’s domain of definition.

Published
2023
Full Text
View/download PDF

30. Measurements in Proof Nets as Higher-Order Quantum Circuits

Author

Yoshimizu, Akira, Hasuo, Ichiro, Faggian, Claudia, Dal Lago, Ugo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Shao, Zhong, editor

Published
2014
Full Text
View/download PDF

31. On Probabilistic Applicative Bisimulation and Call-by-Value λ-Calculi

Author

Crubillé, Raphaëlle, Dal Lago, Ugo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Shao, Zhong, editor

Published
2014
Full Text
View/download PDF

32. Probabilistic Recursion Theory and Implicit Computational Complexity

Author

Dal Lago, Ugo, Zuppiroli, Sara, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Ciobanu, Gabriel, editor, and Méry, Dominique, editor

Published
2014
Full Text
View/download PDF

36. Open Higher-Order Logic

Author

Dal Lago, Ugo, Gavazzo, Francesco, and Ghyselen, Alexis

Subjects
First-Order Properties, Theory of computation → Higher order logic, Formal Verification, Relational Logic, Theory of computation → Logic and verification
Abstract

We introduce a variation on Barthe et al.’s higher-order logic in which formulas are interpreted as predicates over open rather than closed objects. This way, concepts which have an intrinsically functional nature, like continuity, differentiability, or monotonicity, can be expressed and reasoned about in a very natural way, following the structure of the underlying program. We give open higher-order logic in distinct flavors, and in particular in its relational and local versions, the latter being tailored for situations in which properties hold only in part of the underlying function’s domain of definition., LIPIcs, Vol. 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023), pages 17:1-17:17

Published
2023
Full Text
View/download PDF

37. On the Lattice of Program Metrics

Author

Dal Lago, Ugo, Hoshino, Naohiko, and Pistone, Paolo

Subjects
Linear Types, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Theory of computation → Program semantics, Metrics, Lambda Calculus, Logic in Computer Science (cs.LO)
Abstract

In this paper we are concerned with understanding the nature of program metrics for calculi with higher-order types, seen as natural generalizations of program equivalences. Some of the metrics we are interested in are well-known, such as those based on the interpretation of terms in metric spaces and those obtained by generalizing observational equivalence. We also introduce a new one, called the interactive metric, built by applying the well-known Int-Construction to the category of metric complete partial orders. Our aim is then to understand how these metrics relate to each other, i.e., whether and in which cases one such metric refines another, in analogy with corresponding well-studied problems about program equivalences. The results we obtain are twofold. We first show that the metrics of semantic origin, i.e., the denotational and interactive ones, lie in between the observational and equational metrics and that in some cases, these inclusions are strict. Then, we give a result about the relationship between the denotational and interactive metrics, revealing that the former is less discriminating than the latter. All our results are given for a linear lambda-calculus, and some of them can be generalized to calculi with graded comonads, in the style of Fuzz., LIPIcs, Vol. 260, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023), pages 20:1-20:19

Published
2023
Full Text
View/download PDF

38. Complexity Analysis in Presence of Control Operators and Higher-Order Functions

Author

Dal Lago, Ugo, Pellitta, Giulio, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, McMillan, Ken, editor, Middeldorp, Aart, editor, and Voronkov, Andrei, editor

Published
2013
Full Text
View/download PDF

39. A Higher-Order Characterization of Probabilistic Polynomial Time

Author

Dal Lago, Ugo, Parisen Toldin, Paolo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Peña, Ricardo, editor, van Eekelen, Marko, editor, and Shkaravska, Olha, editor

Published
2012
Full Text
View/download PDF

40. A Short Introduction to Implicit Computational Complexity

Author

Dal Lago, Ugo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bezhanishvili, Nick, editor, and Goranko, Valentin, editor

Published
2012
Full Text
View/download PDF

45. Type Inference for Sublinear Space Functional Programming

Author

Dal Lago, Ugo, Schöpp, Ulrich, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Ueda, Kazunori, editor

Published
2010
Full Text
View/download PDF

46. Derivational Complexity Is an Invariant Cost Model

Author

Dal Lago, Ugo, Martini, Simone, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, van Eekelen, Marko, editor, and Shkaravska, Olha, editor

Published
2010
Full Text
View/download PDF

47. Functional Programming in Sublinear Space

Author

Dal Lago, Ugo, Schöpp, Ulrich, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Gordon, Andrew D., editor

Published
2010
Full Text
View/download PDF

49. On Constructor Rewrite Systems and the Lambda-Calculus

Author

Dal Lago, Ugo, Martini, Simone, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Albers, Susanne, editor, Marchetti-Spaccamela, Alberto, editor, Matias, Yossi, editor, Nikoletseas, Sotiris, editor, and Thomas, Wolfgang, editor

Published
2009
Full Text
View/download PDF

50. Bounded Linear Logic, Revisited

Author

Dal Lago, Ugo, Hofmann, Martin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Curien, Pierre-Louis, editor

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results