Giselle Reis
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Giselle Reis has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Amy Felty
University of Ottawa
1 shared publication - Bruno Woltzenlogel Paleo
Australian National University
1 shared publication - Carlos Olarte
Université Sorbonne Paris Nord
1 shared publication - Dragiša Žunić
Carnegie Mellon University
1 shared publication - Elaine Pimentel
Department of Computer Science, University College London, London, UK
1 shared publication - Harald Ruess
SRIs Computer Science Lab in Menlo Park, CA, USA
1 shared publication
Latest Publications
- Open Access
- 1 October 2022
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 32 (9) , 1117-1118
Preface to Special Issue: LSFA 2019 and 2020
Logical and semantic frameworks are formal languages used to represent logics, languages, and systems. These frameworks provide foundations for formal specification of systems and programming languages, supporting tool development and reasoning. LSFA aims to be a forum for presenting and discussing work in progress and therefore to provide feedback to authors on their preliminary research. Topics of interest to this forum include, but are not limited to, specification languages and metalanguages , formal semantics of languages and logical systems, logical frameworks, semantic frameworks, type theory, proof theory, automated deduction, implementation of logical or semantic frameworks, applications of logical or semantic frameworks, computational and logical properties of semantic frameworks, logical aspects of computational complexity, lambda and combinatory calculi, and process calculi. Out of the total of 21 papers that were presented at LSFA 2019 and 2020, 13 were invited to submit an extended version to this special issue. The invited speakers were also invited to submit. Ten manuscripts were submitted, of which six were selected for inclusion in the issue. All the submitted manuscripts were subjected to rigorous review, with some going through multiple stages of revision. The first article by Sandro Preto and Marcelo Finger, entitled "Efficient Representation of Piecewise Linear Functions into Łukasiewicz Logic Modulo Satisfiability" considers rational McNaughton functions and their representation in Łukasiewicz Infinitely-Valued Logic, with a goal of providing a setting for stating and reasoning about properties of such functions. Working toward this goal, the authors focus on two different efficient representations. The paper presents a polynomial algorithm for representing such functions, discusses an implementation, and presents some experimental results. The article by Uwe Wolter, Alfio Martini, and Edward Haeusler, entitled "Indexed and Fibred Structures for Partial and Total Correctness Assertions" studies partial and total correctness assertions in Hoare logic in the context of category theory. The authors show how indexed and fibered structures can be used to model and reason about logical systems. In particular, the syntactic features of Hoare assertions are presented in the setting of indexed categories, while Hoare triples and the Hoare deduction calculus are characterized in the fibered setting. The third article, by Bruno Xavier, Carlos Olarte, and Elaine Pimentel on "A Linear Logic Framework for Multi-Modal Logics" proves cut-admissibility of LNS FMLL and formalizes the proof in Coq. LNS FMLL is a focused, linear, nested system for FMLL, which is a multi-modal linear logic.
- 1 October 2022
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 32 (9) , 1117-1118
Open AccessPreface to Special Issue: LSFA 2019 and 2020
Logical and semantic frameworks are formal languages used to represent logics, languages, and systems. These frameworks provide foundations for formal specification of systems and programming languages, supporting tool development and reasoning. LSFA aims to be a forum for presenting and discussing work in progress and therefore to provide feedback to authors on their preliminary research. Topics of interest to this forum include, but are not limited to, specification languages and metalanguages , formal semantics of languages and logical systems, logical frameworks, semantic frameworks, type theory, proof theory, automated deduction, implementation of logical or semantic frameworks, applications of logical or semantic frameworks, computational and logical properties of semantic frameworks, logical aspects of computational complexity, lambda and combinatory calculi, and process calculi. Out of the total of 21 papers that were presented at LSFA 2019 and 2020, 13 were invited to submit an extended version to this special issue. The invited speakers were also invited to submit. Ten manuscripts were submitted, of which six were selected for inclusion in the issue. All the submitted manuscripts were subjected to rigorous review, with some going through multiple stages of revision. The first article by Sandro Preto and Marcelo Finger, entitled "Efficient Representation of Piecewise Linear Functions into Łukasiewicz Logic Modulo Satisfiability" considers rational McNaughton functions and their representation in Łukasiewicz Infinitely-Valued Logic, with a goal of providing a setting for stating and reasoning about properties of such functions. Working toward this goal, the authors focus on two different efficient representations. The paper presents a polynomial algorithm for representing such functions, discusses an implementation, and presents some experimental results. The article by Uwe Wolter, Alfio Martini, and Edward Haeusler, entitled "Indexed and Fibred Structures for Partial and Total Correctness Assertions" studies partial and total correctness assertions in Hoare logic in the context of category theory. The authors show how indexed and fibered structures can be used to model and reason about logical systems. In particular, the syntactic features of Hoare assertions are presented in the setting of indexed categories, while Hoare triples and the Hoare deduction calculus are characterized in the fibered setting. The third article, by Bruno Xavier, Carlos Olarte, and Elaine Pimentel on "A Linear Logic Framework for Multi-Modal Logics" proves cut-admissibility of LNS FMLL and formalizes the proof in Coq. LNS FMLL is a focused, linear, nested system for FMLL, which is a multi-modal linear logic.
- Open Access
- 5 July 2021
- Published by Springer Nature
- p. 234-251
Proof Search and Certificates for Evidential Transactions
Attestation logics have been used for specifying systems with policies involving different principals. Cyberlogic is an attestation logic used for the specification of Evidential Transactions (ETs). In such transactions, evidence has to be provided supporting its validity with respect to given policies. For example, visa applicants may be required to demonstrate that they have sufficient funds to visit a foreign country. Such evidence can be expressed as a Cyberlogic proof, possibly combined with non-logical data (e.g., a digitally signed document). A key issue is how to construct and communicate such evidence/proofs. It turns out that attestation modalities are challenging to use established proof-theoretic methods such as focusing. Our first contribution is the refinement of Cyberlogic proof theory with knowledge operators which can be used to represent knowledge bases local to one or more principals. Our second contribution is the identification of an executable fragment of Cyberlogic, called Cyberlogic programs, enabling the specification of ETs. Our third contribution is a sound and complete proof system for Cyberlogic programs enabling proof search similar to search in logic programming. Our final contribution is a proof certificate format for Cyberlogic programs inspired by Foundational Proof Certificates as a means to communicate evidence and check its validity.
- 5 July 2021
- Published by Springer Nature
- p. 234-251
Open AccessProof Search and Certificates for Evidential Transactions
Attestation logics have been used for specifying systems with policies involving different principals. Cyberlogic is an attestation logic used for the specification of Evidential Transactions (ETs). In such transactions, evidence has to be provided supporting its validity with respect to given policies. For example, visa applicants may be required to demonstrate that they have sufficient funds to visit a foreign country. Such evidence can be expressed as a Cyberlogic proof, possibly combined with non-logical data (e.g., a digitally signed document). A key issue is how to construct and communicate such evidence/proofs. It turns out that attestation modalities are challenging to use established proof-theoretic methods such as focusing. Our first contribution is the refinement of Cyberlogic proof theory with knowledge operators which can be used to represent knowledge bases local to one or more principals. Our second contribution is the identification of an executable fragment of Cyberlogic, called Cyberlogic programs, enabling the specification of ETs. Our third contribution is a sound and complete proof system for Cyberlogic programs enabling proof search similar to search in logic programming. Our final contribution is a proof certificate format for Cyberlogic programs inspired by Foundational Proof Certificates as a means to communicate evidence and check its validity.
- 24 June 2020
- Published by Springer Nature
- Vol. 12167, 480-488
Sequoia: A Playground for Logicians
Sequent calculus is a pervasive technique for studying logics and their properties due to the regularity of rules, proofs, and meta-property proofs across logics. However, even simple proofs can be large, and writing them by hand is often messy. Moreover, the combinatorial nature of the calculus makes it easy for humans to make mistakes or miss cases. Sequoia aims to alleviate these problems. Sequoia is a web-based application for specifying sequent calculi and performing basic reasoning about them. The goal is to be a user-friendly program, where logicians can specify and “play” with their calculi. For that purpose, we provide an intuitive interface where inference rules can be input in Open image in new window and are immediately rendered with the corresponding symbols. Users can then build proof trees in a streamlined and minimal-effort way, in whichever calculus they defined. In addition to that, we provide checks for some of the most important meta-theoretical properties, such as weakening admissibility and identity expansion, given that they proceed by the usual structural induction. In this sense, the logician is only left with the tricky and most interesting cases of each analysis.
- 24 June 2020
- Published by Springer Nature
- Vol. 12167, 480-488
Sequoia: A Playground for Logicians
Sequent calculus is a pervasive technique for studying logics and their properties due to the regularity of rules, proofs, and meta-property proofs across logics. However, even simple proofs can be large, and writing them by hand is often messy. Moreover, the combinatorial nature of the calculus makes it easy for humans to make mistakes or miss cases. Sequoia aims to alleviate these problems. Sequoia is a web-based application for specifying sequent calculi and performing basic reasoning about them. The goal is to be a user-friendly program, where logicians can specify and “play” with their calculi. For that purpose, we provide an intuitive interface where inference rules can be input in Open image in new window and are immediately rendered with the corresponding symbols. Users can then build proof trees in a streamlined and minimal-effort way, in whichever calculus they defined. In addition to that, we provide checks for some of the most important meta-theoretical properties, such as weakening admissibility and identity expansion, given that they proceed by the usual structural induction. In this sense, the logician is only left with the tricky and most interesting cases of each analysis.
- 1 August 2019
- Published by Elsevier in Theoretical Computer Science
- Vol. 781, 24-38
Formalized meta-theory of sequent calculi for linear logics
- 1 August 2019
- Published by Elsevier in Theoretical Computer Science
- Vol. 781, 24-38
Formalized meta-theory of sequent calculi for linear logics
- Open Access
- 15 April 2019
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 292, 1-14
Formalization of Automated Trading Systems in a Concurrent Linear Framework
We present a declarative and modular specification of an automated trading system (ATS) in the concurrent linear framework CLF. We implemented it in Celf, a CLF type checker which also supports executing CLF specifications. We outline the verification of two representative properties of trading systems using generative grammars, an approach to reasoning about CLF specifications.
- 15 April 2019
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 292, 1-14
Open AccessFormalization of Automated Trading Systems in a Concurrent Linear Framework
We present a declarative and modular specification of an automated trading system (ATS) in the concurrent linear framework CLF. We implemented it in Celf, a CLF type checker which also supports executing CLF specifications. We outline the verification of two representative properties of trading systems using generative grammars, an approach to reasoning about CLF specifications.
- Open Access
- 15 April 2019
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 292, 118-132
The ILLTP Library for Intuitionistic Linear Logic
Benchmarking automated theorem proving (ATP) systems using standardized problem sets is a wellestablished method for measuring their performance. However, the availability of such libraries for non-classical logics is very limited. In this work we propose a library for benchmarking Girard's (propositional) intuitionistic linear logic. For a quick bootstrapping of the collection of problems, and for discussing the selection of relevant problems and understanding their meaning as linear logic theorems, we use translations of the collection of Kleene's intuitionistic theorems in the traditional monograph "Introduction to Metamathematics". We analyze four different translations of intuitionistic logic into linear logic and compare their proofs using a linear logic based prover with focusing. In order to enhance the set of problems in our library, we apply the three provability-preserving translations to the propositional benchmarks in the ILTP Library. Finally, we generate a comprehensive set of reachability problems for Petri nets and encode such problems as linear logic sequents, thus enlarging our collection of problems.
- 15 April 2019
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 292, 118-132
Open AccessThe ILLTP Library for Intuitionistic Linear Logic
Benchmarking automated theorem proving (ATP) systems using standardized problem sets is a wellestablished method for measuring their performance. However, the availability of such libraries for non-classical logics is very limited. In this work we propose a library for benchmarking Girard's (propositional) intuitionistic linear logic. For a quick bootstrapping of the collection of problems, and for discussing the selection of relevant problems and understanding their meaning as linear logic theorems, we use translations of the collection of Kleene's intuitionistic theorems in the traditional monograph "Introduction to Metamathematics". We analyze four different translations of intuitionistic logic into linear logic and compare their proofs using a linear logic based prover with focusing. In order to enhance the set of problems in our library, we apply the three provability-preserving translations to the propositional benchmarks in the ILTP Library. Finally, we generate a comprehensive set of reachability problems for Petri nets and encode such problems as linear logic sequents, thus enlarging our collection of problems.
- 16 January 2019
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 29 (8) , 1061-1091
Complexity of translations from resolution to sequent calculus
Resolution and sequent calculus are two well-known formal proof systems. Their differences make them suitable for distinct tasks. Resolution and its variants are very efficient for automated reasoning and are in fact the theoretical basis of many theorem provers. However, being intentionally machine oriented, the resolution calculus is not as natural for human beings and the input problem needs to be pre-processed to clause normal form. Sequent calculus, on the other hand, is a modular formalism that is useful for analysing meta-properties of various logics and is, therefore, popular among proof theorists. The input problem does not need to be pre-processed, and proofs are more detailed. However, proofs also tend to be larger and more verbose. When the worlds of proof theory and automated theorem proving meet, translations between resolution and sequent calculus are often necessary. In this paper, we compare three translation methods and analyse their complexity.
- 16 January 2019
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 29 (8) , 1061-1091
Complexity of translations from resolution to sequent calculus
Resolution and sequent calculus are two well-known formal proof systems. Their differences make them suitable for distinct tasks. Resolution and its variants are very efficient for automated reasoning and are in fact the theoretical basis of many theorem provers. However, being intentionally machine oriented, the resolution calculus is not as natural for human beings and the input problem needs to be pre-processed to clause normal form. Sequent calculus, on the other hand, is a modular formalism that is useful for analysing meta-properties of various logics and is, therefore, popular among proof theorists. The input problem does not need to be pre-processed, and proofs are more detailed. However, proofs also tend to be larger and more verbose. When the worlds of proof theory and automated theorem proving meet, translations between resolution and sequent calculus are often necessary. In this paper, we compare three translation methods and analyse their complexity.