Lucas Martinelli Tabajara
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Lucas Martinelli Tabajara has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Moshe Y. Vardi
Rice University, Houston, TX, USA
5 shared publications - Yi Lin
Rice University 77005 Houston TX USA
2 shared publications - Andrew M. Wells
Amazon Web Services, Santa Clara, United States
1 shared publication - Antonio Di Stasio
University of Oxford
1 shared publication Dror Fried
Rice University
1 shared publication- Dror Fried
Department of Mathematics and Computer Science The Open University of Israel Israel
1 shared publication
Latest Publications
- Open Access
- 26 July 2024
- Published by Springer Nature
- p. 112-134
Dynamic Programming for Symbolic Boolean Realizability and Synthesis
Inspired by recent progress in dynamic programming approaches for weighted model counting, we investigate a dynamic-programming approach in the context of boolean realizability and synthesis, which takes a conjunctive-normal-form boolean formula over input and output variables, and aims at synthesizing witness functions for the output variables in terms of the inputs. We show how graded project-join trees, obtained via tree decomposition, can be used to compute a BDD representing the realizability set for the input formulas in a bottom-up order. We then show how the intermediate BDDs generated during realizability checking phase can be applied to synthesizing the witness functions in a top-down manner. An experimental evaluation of a solver – DPSynth – based on these ideas demonstrates that our approach for Boolean realizabilty and synthesis has superior time and space performance over a heuristics-based approach using same symbolic representations. We discuss the advantage on scalability of the new approach, and also investigate our findings on the performance of the DP framework.
- 26 July 2024
- Published by Springer Nature
- p. 112-134
Open AccessDynamic Programming for Symbolic Boolean Realizability and Synthesis
Inspired by recent progress in dynamic programming approaches for weighted model counting, we investigate a dynamic-programming approach in the context of boolean realizability and synthesis, which takes a conjunctive-normal-form boolean formula over input and output variables, and aims at synthesizing witness functions for the output variables in terms of the inputs. We show how graded project-join trees, obtained via tree decomposition, can be used to compute a BDD representing the realizability set for the input formulas in a bottom-up order. We then show how the intermediate BDDs generated during realizability checking phase can be applied to synthesizing the witness functions in a top-down manner. An experimental evaluation of a solver – DPSynth – based on these ideas demonstrates that our approach for Boolean realizabilty and synthesis has superior time and space performance over a heuristics-based approach using same symbolic representations. We discuss the advantage on scalability of the new approach, and also investigate our findings on the performance of the DP framework.
- 22 October 2023
- Published by Springer Nature
- p. 227-247
Model Checking Strategies from Synthesis over Finite Traces
- 22 October 2023
- Published by Springer Nature
- p. 227-247
Model Checking Strategies from Synthesis over Finite Traces
- Open Access
- 1 December 2022
- Published by Springer Nature in Formal Methods in System Design
- Vol. 61 (2-3) , 139-163
Finite-trace and generalized-reactivity specifications in temporal synthesis
Linear Temporal Logic (LTL) synthesis aims at automatically synthesizing a program that complies with desired properties expressed in LTL. Unfortunately it has been proved to be too difficult computationally to perform full LTL synthesis. There have been two success stories with LTL synthesis, both having to do with the form of the specification. The first is the GR(1) approach: use safety conditions to determine the possible transitions in a game between the environment and the agent, plus one powerful notion of fairness, Generalized Reactivity(1), or GR(1). The second, inspired by AI planning, is focusing on finite-trace temporal synthesis, with LTL $$_f$$ (LTL on finite traces) as the specification language. In this paper we take these two lines of work and bring them together. We first study the case in which we have an LTL $$_f$$ agent goal and a GR(1) environment specification. We then add to the framework safety conditions for both the environment and the agent, obtaining a highly expressive yet still scalable form of LTL synthesis.- 1 December 2022
- Published by Springer Nature in Formal Methods in System Design
- Vol. 61 (2-3) , 139-163
Open AccessFinite-trace and generalized-reactivity specifications in temporal synthesis
Linear Temporal Logic (LTL) synthesis aims at automatically synthesizing a program that complies with desired properties expressed in LTL. Unfortunately it has been proved to be too difficult computationally to perform full LTL synthesis. There have been two success stories with LTL synthesis, both having to do with the form of the specification. The first is the GR(1) approach: use safety conditions to determine the possible transitions in a game between the environment and the agent, plus one powerful notion of fairness, Generalized Reactivity(1), or GR(1). The second, inspired by AI planning, is focusing on finite-trace temporal synthesis, with LTL $$_f$$ (LTL on finite traces) as the specification language. In this paper we take these two lines of work and bring them together. We first study the case in which we have an LTL $$_f$$ agent goal and a GR(1) environment specification. We then add to the framework safety conditions for both the environment and the agent, obtaining a highly expressive yet still scalable form of LTL synthesis. - 1 April 2022
- Published by Springer Nature in Formal Methods in System Design
- Vol. 60 (2) , 228-258
Functional synthesis via input–output separation
- 1 April 2022
- Published by Springer Nature in Formal Methods in System Design
- Vol. 60 (2) , 228-258
Functional synthesis via input–output separation
- Open Access
- 30 March 2022
- Published by Springer Nature
- p. 64-83
ZDD Boolean Synthesis
Motivated by applications in boolean-circuit design, boolean synthesis is the process of synthesizing a boolean function with multiple outputs, given a relation between its inputs and outputs. Previous work has attempted to solve boolean functional synthesis by converting a specification formula into a Binary Decision Diagram (BDD) and quantifying existentially the output variables. We make use of the fact that the specification is usually given in the form of a Conjunctive Normal Form (CNF) formula, and we can perform resolution on a symbolic representation of a CNF formula in the form of a Zero-suppressed Binary Decision Diagram (ZDD). We adapt the realizability test to the context of CNF and ZDD, and show that theCrossoperation defined in earlier work can be used for witness construction. Experiments show that our approach is complementary to BDD-based Boolean synthesis.
- 30 March 2022
- Published by Springer Nature
- p. 64-83
Open AccessZDD Boolean Synthesis
Motivated by applications in boolean-circuit design, boolean synthesis is the process of synthesizing a boolean function with multiple outputs, given a relation between its inputs and outputs. Previous work has attempted to solve boolean functional synthesis by converting a specification formula into a Binary Decision Diagram (BDD) and quantifying existentially the output variables. We make use of the fact that the specification is usually given in the form of a Conjunctive Normal Form (CNF) formula, and we can perform resolution on a symbolic representation of a CNF formula in the form of a Zero-suppressed Binary Decision Diagram (ZDD). We adapt the realizability test to the context of CNF and ZDD, and show that theCrossoperation defined in earlier work can be used for witness construction. Experiments show that our approach is complementary to BDD-based Boolean synthesis.
- Open Access
Witnessing Secure Compilation
Compiler optimizations are designed to improve run-time performance while preserving input-output behavior. Correctness in this sense does not necessarily preserve security: it is known that standard optimizations may break or weaken security properties that hold of the source program. This work develops a translation validation method for secure compilation. Security (hyper-)properties are expressed using automata operating over a bundle of program traces. A flexible, automaton-based refinement scheme, generalizing existing refinement methods, guarantees that the associated security property is preserved by a program transformation. In practice, the refinement relations ("security witnesses") can be generated during compilation and validated independently with a refinement checker. This process is illustrated for common optimizations. Crucially, it is not necessary to verify the compiler implementation itself, which is infeasible in practice for production compilers.
Open AccessWitnessing Secure Compilation
Compiler optimizations are designed to improve run-time performance while preserving input-output behavior. Correctness in this sense does not necessarily preserve security: it is known that standard optimizations may break or weaken security properties that hold of the source program. This work develops a translation validation method for secure compilation. Security (hyper-)properties are expressed using automata operating over a bundle of program traces. A flexible, automaton-based refinement scheme, generalizing existing refinement methods, guarantees that the associated security property is preserved by a program transformation. In practice, the refinement relations ("security witnesses") can be generated during compilation and validated independently with a refinement checker. This process is illustrated for common optimizations. Crucially, it is not necessary to verify the compiler implementation itself, which is infeasible in practice for production compilers.