Deepak Kapur
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
Deepak Kapur has a total of 47 co-authors. Here are the top co-authors by number of shared publications:
- Naijun Zhan
Peking University
3 shared publications - Alessandro Gianola
INESC-ID/Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal
2 shared publications - Darko Stefanovic
Affiliations Department of Computer Science, University of New Mexico, Albuquerque, New Mexico, United States of America, Department of Chemical and Biological Engineering, University of New Mexico, Albuquerque, New Mexico, United States of America
2 shared publications - Franz Baader
TU Dresden
2 shared publications - Roli Varma
University of New Mexico
2 shared publications - Silvio Ghilardi
Università degli Studi di Milano
2 shared publications
Latest Publications
- 20 November 2023
- Published by American Physical Society (APS) in Physical Review A
- Vol. 108 (5) , 052609
Verifying quantum phase estimation using an expressive theorem-proving assistant
The general-purpose interactive theorem-proving assistant called prove-it was used to verify the quantum phase estimation (QPE) algorithm, specifically claims about its outcome probabilities. prove-it is unique in its ability to express sophisticated mathematical statements, including statements about quantum circuits, integrated firmly within its formal theorem-proving framework. We demonstrate our ability to follow a textbook proof to produce a formally certified proof, highlighting useful automation features to fill in obvious steps and make formal proving nearly as straightforward as informal theorem proving. Finally, we make comparisons with formal theorem proving in other systems where similar claims about QPE have been proven.
- 20 November 2023
- Published by American Physical Society (APS) in Physical Review A
- Vol. 108 (5) , 052609
Verifying quantum phase estimation using an expressive theorem-proving assistant
The general-purpose interactive theorem-proving assistant called prove-it was used to verify the quantum phase estimation (QPE) algorithm, specifically claims about its outcome probabilities. prove-it is unique in its ability to express sophisticated mathematical statements, including statements about quantum circuits, integrated firmly within its formal theorem-proving framework. We demonstrate our ability to follow a textbook proof to produce a formally certified proof, highlighting useful automation features to fill in obvious steps and make formal proving nearly as straightforward as informal theorem proving. Finally, we make comparisons with formal theorem proving in other systems where similar claims about QPE have been proven.
- Open Access
- 9 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 24 (4) , 1-33
Interpolation Results for Arrays with Length and MaxDiff
In this article, we enrich McCarthy’s theory of extensional arrays with a length and a maxdiff operation. As is well-known, some diff operation (i.e., some kind of difference function showing where two unequal arrays differ) is needed to keep interpolants quantifier free in array theories. Our maxdiff operation returns the max index where two arrays differ; thus, it has a univocally determined semantics. The length function is a natural complement of such a maxdiff operation and is needed to handle real arrays. Obtaining interpolation results for such a rich theory is a surprisingly hard task. We get such results via a thorough semantic analysis of the models of the theory and of their amalgamation and strong amalgamation properties. The results are modular with respect to the index theory; we show how to convert them into concrete interpolation algorithms via a hierarchical approach realizing a polynomial reduction to interpolation in linear arithmetics endowed with free function symbols.
- 9 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 24 (4) , 1-33
Open AccessInterpolation Results for Arrays with Length and MaxDiff
In this article, we enrich McCarthy’s theory of extensional arrays with a length and a maxdiff operation. As is well-known, some diff operation (i.e., some kind of difference function showing where two unequal arrays differ) is needed to keep interpolants quantifier free in array theories. Our maxdiff operation returns the max index where two arrays differ; thus, it has a univocally determined semantics. The length function is a natural complement of such a maxdiff operation and is needed to handle real arrays. Obtaining interpolation results for such a rich theory is a surprisingly hard task. We get such results via a thorough semantic analysis of the models of the theory and of their amalgamation and strong amalgamation properties. The results are modular with respect to the index theory; we show how to convert them into concrete interpolation algorithms via a hierarchical approach realizing a polynomial reduction to interpolation in linear arithmetics endowed with free function symbols.
- Open Access
- 7 May 2022
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 66 (3) , 301-329
Deciding the Word Problem for Ground and Strongly Shallow Identities w.r.t. Extensional Symbols
The word problem for a finite set of ground identities is known to be decidable in polynomial time using congruence closure, and this is also the case if some of the function symbols are assumed to be commutative or defined by certain shallow identities, called strongly shallow. We show that decidability in P is preserved if we add the assumption that certain function symbolsfareextensionalin the sense that $$f(s_1,\ldots ,s_n) \mathrel {\approx }f(t_1,\ldots ,t_n)$$ implies $$s_1 \mathrel {\approx }t_1,\ldots ,s_n \mathrel {\approx }t_n$$ . In addition, we investigate a variant of extensionality that is more appropriate for commutative function symbols, but which raises the complexity of the word problem to coNP.- 7 May 2022
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 66 (3) , 301-329
Open AccessDeciding the Word Problem for Ground and Strongly Shallow Identities w.r.t. Extensional Symbols
The word problem for a finite set of ground identities is known to be decidable in polynomial time using congruence closure, and this is also the case if some of the function symbols are assumed to be commutative or defined by certain shallow identities, called strongly shallow. We show that decidability in P is preserved if we add the assumption that certain function symbolsfareextensionalin the sense that $$f(s_1,\ldots ,s_n) \mathrel {\approx }f(t_1,\ldots ,t_n)$$ implies $$s_1 \mathrel {\approx }t_1,\ldots ,s_n \mathrel {\approx }t_n$$ . In addition, we investigate a variant of extensionality that is more appropriate for commutative function symbols, but which raises the complexity of the word problem to coNP. - Open Access
- 23 March 2021
- Published by Springer Nature
- Vol. 12650, 268-288
Interpolation and Amalgamation for Arrays with MaxDiff
In this paper, the theory of McCarthy’s extensional arrays enriched with a maxdiff operation (this operation returns the biggest index where two given arrays differ) is proposed. It is known from the literature that a diff operation is required for the theory of arrays in order to enjoy the Craig interpolation property at the quantifier-free level. However, the diff operation introduced in the literature is merely instrumental to this purpose and has only a purely formal meaning (it is obtained from the Skolemization of the extensionality axiom). Our maxdiff operation significantly increases the level of expressivity; however, obtaining interpolation results for the resulting theory becomes a surprisingly hard task. We obtain such results via a thorough semantic analysis of the models of the theory and of their amalgamation properties. The results are modular with respect to the index theory and it is shown how to convert them into concrete interpolation algorithms via a hierarchical approach.
- 23 March 2021
- Published by Springer Nature
- Vol. 12650, 268-288
Open AccessInterpolation and Amalgamation for Arrays with MaxDiff
In this paper, the theory of McCarthy’s extensional arrays enriched with a maxdiff operation (this operation returns the biggest index where two given arrays differ) is proposed. It is known from the literature that a diff operation is required for the theory of arrays in order to enjoy the Craig interpolation property at the quantifier-free level. However, the diff operation introduced in the literature is merely instrumental to this purpose and has only a purely formal meaning (it is obtained from the Skolemization of the extensionality axiom). Our maxdiff operation significantly increases the level of expressivity; however, obtaining interpolation results for the resulting theory becomes a surprisingly hard task. We obtain such results via a thorough semantic analysis of the models of the theory and of their amalgamation properties. The results are modular with respect to the index theory and it is shown how to convert them into concrete interpolation algorithms via a hierarchical approach.
- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 163-180
Deciding the Word Problem for Ground Identities with Commutative and Extensional Symbols
The word problem for a finite set of ground identities is known to be decidable in polynomial time, and this is also the case if some of the function symbols are assumed to be commutative. We show that decidability in P is preserved if we also assume that certain function symbols f are extensional in the sense that \(f(s_1,\ldots ,s_n) \mathrel {\approx }f(t_1,\ldots ,t_n)\) implies \(s_1 \mathrel {\approx }t_1,\ldots ,s_n \mathrel {\approx }t_n\). In addition, we investigate a variant of extensionality that is more appropriate for commutative function symbols, but which raises the complexity of the word problem to coNP.- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 163-180
Deciding the Word Problem for Ground Identities with Commutative and Extensional Symbols
The word problem for a finite set of ground identities is known to be decidable in polynomial time, and this is also the case if some of the function symbols are assumed to be commutative. We show that decidability in P is preserved if we also assume that certain function symbols f are extensional in the sense that \(f(s_1,\ldots ,s_n) \mathrel {\approx }f(t_1,\ldots ,t_n)\) implies \(s_1 \mathrel {\approx }t_1,\ldots ,s_n \mathrel {\approx }t_n\). In addition, we investigate a variant of extensionality that is more appropriate for commutative function symbols, but which raises the complexity of the word problem to coNP.- Open Access
An Algorithm for Computing a Minimal Comprehensive Gröbner\, Basis of a Parametric Polynomial System
An algorithm to generate a minimal comprehensive Gr\"obner\, basis of a parametric polynomial system from an arbitrary faithful comprehensive Gr\"obner\, system is presented. A basis of a parametric polynomial ideal is a comprehensive Gr\"obner\, basis if and only if for every specialization of parameters in a given field, the specialization of the basis is a Gr\"obner\, basis of the associated specialized polynomial ideal. The key idea used in ensuring minimality is that of a polynomial being essential with respect to a comprehensive Gr\"obner\, basis. The essentiality check is performed by determining whether a polynomial can be covered for various specializations by other polynomials in the associated branches in a comprehensive Gr\"obner\, system. The algorithm has been implemented and successfully tried on many examples from the literature.
Open AccessAn Algorithm for Computing a Minimal Comprehensive Gröbner\, Basis of a Parametric Polynomial System
An algorithm to generate a minimal comprehensive Gr\"obner\, basis of a parametric polynomial system from an arbitrary faithful comprehensive Gr\"obner\, system is presented. A basis of a parametric polynomial ideal is a comprehensive Gr\"obner\, basis if and only if for every specialization of parameters in a given field, the specialization of the basis is a Gr\"obner\, basis of the associated specialized polynomial ideal. The key idea used in ensuring minimality is that of a polynomial being essential with respect to a comprehensive Gr\"obner\, basis. The essentiality check is performed by determining whether a polynomial can be covered for various specializations by other polynomials in the associated branches in a comprehensive Gr\"obner\, system. The algorithm has been implemented and successfully tried on many examples from the literature.
- Open Access
Connecting Program Synthesis and Reachability: Automatic Program Repair using Test-Input Generation
We prove that certain formulations of program synthesis and reachability are equivalent. Specifically, our constructive proof shows the reductions between the template-based synthesis problem, which generates a program in a pre-specified form, and the reachability problem, which decides the reachability of a program location. This establishes a link between the two research fields and allows for the transfer of techniques and results between them. To demonstrate the equivalence, we develop a program repair prototype using reachability tools. We transform a buggy program and its required specification into a specific program containing a location reachable only when the original program can be repaired, and then apply an off-the-shelf test-input generation tool on the transformed program to find test values to reach the desired location. Those test values correspond to repairs for the original programm. Preliminary results suggest that our approach compares favorably to other repair methods.
Open AccessConnecting Program Synthesis and Reachability: Automatic Program Repair using Test-Input Generation
We prove that certain formulations of program synthesis and reachability are equivalent. Specifically, our constructive proof shows the reductions between the template-based synthesis problem, which generates a program in a pre-specified form, and the reachability problem, which decides the reachability of a program location. This establishes a link between the two research fields and allows for the transfer of techniques and results between them. To demonstrate the equivalence, we develop a program repair prototype using reachability tools. We transform a buggy program and its required specification into a specific program containing a location reachable only when the original program can be repaired, and then apply an off-the-shelf test-input generation tool on the transformed program to find test values to reach the desired location. Those test values correspond to repairs for the original programm. Preliminary results suggest that our approach compares favorably to other repair methods.
- 14 February 2019
- Published by Springer Nature in Journal of Systems Science and Complexity
- Vol. 32 (1) , 317-355
Conditional Congruence Closure over Uninterpreted and Interpreted Symbols
- 14 February 2019
- Published by Springer Nature in Journal of Systems Science and Complexity
- Vol. 32 (1) , 317-355
Conditional Congruence Closure over Uninterpreted and Interpreted Symbols
- 14 February 2017
- Published by Springer Nature in Journal of Systems Science and Complexity
- Vol. 30 (1) , 196-233
Comprehensive Gröbner basis theory for a parametric polynomial ideal and the associated completion algorithm
- 14 February 2017
- Published by Springer Nature in Journal of Systems Science and Complexity
- Vol. 30 (1) , 196-233
Comprehensive Gröbner basis theory for a parametric polynomial ideal and the associated completion algorithm