[Agda] ring solver
Ruben Henner Zilibowitz
rzilibowitz at yahoo.com.au
Sun Mar 14 01:22:56 CET 2010
The example I tried was really simple. It was:
lem₂ : ∀ n → _
lem₂ = solve 1 (λ n → con (+ 1) :+ n := con (+ 1) :+ (n :+ con (+ 0))) refl
Now I have implemented a proof that the integers are a commutative ring, and a proof that they are a commutative semiring. If I use the following code:
import Algebra.RingSolver.Simple as Solver
import Algebra.RingSolver.AlmostCommutativeRing as ACR
module ℤSemiringSolver =
Solver (ACR.fromCommutativeSemiring commutativeSemiring)
open ℤSemiringSolver
then the function lem₂ above goes through just fine. But if I use:
module ℤRingSolver =
Solver (ACR.fromCommutativeRing commutativeRing)
open ℤRingSolver
Then agda crashes on lem₂ due to memory allocation failure. So could this be caused by a bug somewhere in the ring solver?
Ruben
On 14/03/2010, at 10:31 AM, Nils Anders Danielsson wrote:
> On 2010-03-13 12:34, Ruben Henner Zilibowitz wrote:
>> I've been trying out the ring solver in Algebra.RingSolver. I've
>> noticed it uses "almost commutative rings" instead of actual rings. Is
>> the code here able to deal with proper rings such as the integers, or
>> only semirings such as the natural numbers?
>
> The ring solver can handle both commutative rings and commutative
> semirings, see Algebra.RingSolver.AlmostCommutativeRing. The idea to use
> "almost commutative rings" comes from a paper by Grégoire and Mahboubi:
> Proving Equalities in a Commutative Ring Done Right in Coq.
>
>> I've actually tried it on the full integers and it just eats up all my
>> computer's memory and never produces any answer.
>
> The ring solver may simply be too inefficient for your example.
>
> --
> /NAD
>
More information about the Agda
mailing list