TPTP Problem File: COM015+4.p
View Solutions
- Solve Problem
%------------------------------------------------------------------------------
% File : COM015+4 : TPTP v8.2.0. Released v4.0.0.
% Domain : Computing Theory
% Problem : Newman's lemma on rewriting systems 03_01, 03 expansion
% Version : Especial.
% English :
% Refs : [VLP07] Verchinine et al. (2007), System for Automated Deduction
% : [PV+07] Paskevich et al. (2007), Reasoning Inside a Formula an
% : [Pas08] Paskevich (2008), Email to G. Sutcliffe
% Source : [Pas08]
% Names : newman_03_01.03 [Pas08]
% Status : Theorem
% Rating : 0.89 v8.1.0, 0.83 v7.5.0, 0.94 v7.4.0, 0.90 v7.1.0, 0.91 v7.0.0, 0.90 v6.4.0, 0.88 v6.3.0, 0.92 v6.1.0, 1.00 v6.0.0, 0.96 v5.4.0, 1.00 v5.2.0, 0.90 v5.0.0, 0.92 v4.1.0, 0.96 v4.0.1, 1.00 v4.0.0
% Syntax : Number of formulae : 17 ( 1 unt; 6 def)
% Number of atoms : 177 ( 11 equ)
% Maximal formula atoms : 65 ( 10 avg)
% Number of connectives : 161 ( 1 ~; 32 |; 91 &)
% ( 6 <=>; 31 =>; 0 <=; 0 <~>)
% Maximal formula depth : 22 ( 9 avg)
% Maximal term depth : 1 ( 1 avg)
% Number of predicates : 12 ( 10 usr; 1 prp; 0-3 aty)
% Number of functors : 1 ( 1 usr; 1 con; 0-0 aty)
% Number of variables : 70 ( 51 !; 19 ?)
% SPC : FOF_THM_RFO_SEQ
% Comments : Problem generated by the SAD system [VLP07]
%------------------------------------------------------------------------------
fof(mElmSort,axiom,
! [W0] :
( aElement0(W0)
=> $true ) ).
fof(mRelSort,axiom,
! [W0] :
( aRewritingSystem0(W0)
=> $true ) ).
fof(mReduct,axiom,
! [W0,W1] :
( ( aElement0(W0)
& aRewritingSystem0(W1) )
=> ! [W2] :
( aReductOfIn0(W2,W0,W1)
=> aElement0(W2) ) ) ).
fof(mWFOrd,axiom,
! [W0,W1] :
( ( aElement0(W0)
& aElement0(W1) )
=> ( iLess0(W0,W1)
=> $true ) ) ).
fof(mTCbr,axiom,
! [W0,W1,W2] :
( ( aElement0(W0)
& aRewritingSystem0(W1)
& aElement0(W2) )
=> ( sdtmndtplgtdt0(W0,W1,W2)
=> $true ) ) ).
fof(mTCDef,definition,
! [W0,W1,W2] :
( ( aElement0(W0)
& aRewritingSystem0(W1)
& aElement0(W2) )
=> ( sdtmndtplgtdt0(W0,W1,W2)
<=> ( aReductOfIn0(W2,W0,W1)
| ? [W3] :
( aElement0(W3)
& aReductOfIn0(W3,W0,W1)
& sdtmndtplgtdt0(W3,W1,W2) ) ) ) ) ).
fof(mTCTrans,axiom,
! [W0,W1,W2,W3] :
( ( aElement0(W0)
& aRewritingSystem0(W1)
& aElement0(W2)
& aElement0(W3) )
=> ( ( sdtmndtplgtdt0(W0,W1,W2)
& sdtmndtplgtdt0(W2,W1,W3) )
=> sdtmndtplgtdt0(W0,W1,W3) ) ) ).
fof(mTCRDef,definition,
! [W0,W1,W2] :
( ( aElement0(W0)
& aRewritingSystem0(W1)
& aElement0(W2) )
=> ( sdtmndtasgtdt0(W0,W1,W2)
<=> ( W0 = W2
| sdtmndtplgtdt0(W0,W1,W2) ) ) ) ).
fof(mTCRTrans,axiom,
! [W0,W1,W2,W3] :
( ( aElement0(W0)
& aRewritingSystem0(W1)
& aElement0(W2)
& aElement0(W3) )
=> ( ( sdtmndtasgtdt0(W0,W1,W2)
& sdtmndtasgtdt0(W2,W1,W3) )
=> sdtmndtasgtdt0(W0,W1,W3) ) ) ).
fof(mCRDef,definition,
! [W0] :
( aRewritingSystem0(W0)
=> ( isConfluent0(W0)
<=> ! [W1,W2,W3] :
( ( aElement0(W1)
& aElement0(W2)
& aElement0(W3)
& sdtmndtasgtdt0(W1,W0,W2)
& sdtmndtasgtdt0(W1,W0,W3) )
=> ? [W4] :
( aElement0(W4)
& sdtmndtasgtdt0(W2,W0,W4)
& sdtmndtasgtdt0(W3,W0,W4) ) ) ) ) ).
fof(mWCRDef,definition,
! [W0] :
( aRewritingSystem0(W0)
=> ( isLocallyConfluent0(W0)
<=> ! [W1,W2,W3] :
( ( aElement0(W1)
& aElement0(W2)
& aElement0(W3)
& aReductOfIn0(W2,W1,W0)
& aReductOfIn0(W3,W1,W0) )
=> ? [W4] :
( aElement0(W4)
& sdtmndtasgtdt0(W2,W0,W4)
& sdtmndtasgtdt0(W3,W0,W4) ) ) ) ) ).
fof(mTermin,definition,
! [W0] :
( aRewritingSystem0(W0)
=> ( isTerminating0(W0)
<=> ! [W1,W2] :
( ( aElement0(W1)
& aElement0(W2) )
=> ( sdtmndtplgtdt0(W1,W0,W2)
=> iLess0(W2,W1) ) ) ) ) ).
fof(mNFRDef,definition,
! [W0,W1] :
( ( aElement0(W0)
& aRewritingSystem0(W1) )
=> ! [W2] :
( aNormalFormOfIn0(W2,W0,W1)
<=> ( aElement0(W2)
& sdtmndtasgtdt0(W0,W1,W2)
& ~ ? [W3] : aReductOfIn0(W3,W2,W1) ) ) ) ).
fof(mTermNF,axiom,
! [W0] :
( ( aRewritingSystem0(W0)
& isTerminating0(W0) )
=> ! [W1] :
( aElement0(W1)
=> ? [W2] : aNormalFormOfIn0(W2,W1,W0) ) ) ).
fof(m__656,hypothesis,
aRewritingSystem0(xR) ).
fof(m__656_01,hypothesis,
( ! [W0,W1,W2] :
( ( aElement0(W0)
& aElement0(W1)
& aElement0(W2)
& aReductOfIn0(W1,W0,xR)
& aReductOfIn0(W2,W0,xR) )
=> ? [W3] :
( aElement0(W3)
& ( W1 = W3
| ( ( aReductOfIn0(W3,W1,xR)
| ? [W4] :
( aElement0(W4)
& aReductOfIn0(W4,W1,xR)
& sdtmndtplgtdt0(W4,xR,W3) ) )
& sdtmndtplgtdt0(W1,xR,W3) ) )
& sdtmndtasgtdt0(W1,xR,W3)
& ( W2 = W3
| ( ( aReductOfIn0(W3,W2,xR)
| ? [W4] :
( aElement0(W4)
& aReductOfIn0(W4,W2,xR)
& sdtmndtplgtdt0(W4,xR,W3) ) )
& sdtmndtplgtdt0(W2,xR,W3) ) )
& sdtmndtasgtdt0(W2,xR,W3) ) )
& isLocallyConfluent0(xR)
& ! [W0,W1] :
( ( aElement0(W0)
& aElement0(W1) )
=> ( ( aReductOfIn0(W1,W0,xR)
| ? [W2] :
( aElement0(W2)
& aReductOfIn0(W2,W0,xR)
& sdtmndtplgtdt0(W2,xR,W1) )
| sdtmndtplgtdt0(W0,xR,W1) )
=> iLess0(W1,W0) ) )
& isTerminating0(xR) ) ).
fof(m__,conjecture,
! [W0,W1,W2] :
( ( aElement0(W0)
& aElement0(W1)
& aElement0(W2)
& ( W0 = W1
| ( ( aReductOfIn0(W1,W0,xR)
| ? [W3] :
( aElement0(W3)
& aReductOfIn0(W3,W0,xR)
& sdtmndtplgtdt0(W3,xR,W1) ) )
& sdtmndtplgtdt0(W0,xR,W1) ) )
& sdtmndtasgtdt0(W0,xR,W1)
& ( W0 = W2
| ( ( aReductOfIn0(W2,W0,xR)
| ? [W3] :
( aElement0(W3)
& aReductOfIn0(W3,W0,xR)
& sdtmndtplgtdt0(W3,xR,W2) ) )
& sdtmndtplgtdt0(W0,xR,W2) ) )
& sdtmndtasgtdt0(W0,xR,W2) )
=> ( ! [W3,W4,W5] :
( ( aElement0(W3)
& aElement0(W4)
& aElement0(W5)
& ( W3 = W4
| aReductOfIn0(W4,W3,xR)
| ? [W6] :
( aElement0(W6)
& aReductOfIn0(W6,W3,xR)
& sdtmndtplgtdt0(W6,xR,W4) )
| sdtmndtplgtdt0(W3,xR,W4)
| sdtmndtasgtdt0(W3,xR,W4) )
& ( W3 = W5
| aReductOfIn0(W5,W3,xR)
| ? [W6] :
( aElement0(W6)
& aReductOfIn0(W6,W3,xR)
& sdtmndtplgtdt0(W6,xR,W5) )
| sdtmndtplgtdt0(W3,xR,W5)
| sdtmndtasgtdt0(W3,xR,W5) ) )
=> ( iLess0(W3,W0)
=> ? [W6] :
( aElement0(W6)
& ( W4 = W6
| ( ( aReductOfIn0(W6,W4,xR)
| ? [W7] :
( aElement0(W7)
& aReductOfIn0(W7,W4,xR)
& sdtmndtplgtdt0(W7,xR,W6) ) )
& sdtmndtplgtdt0(W4,xR,W6) ) )
& sdtmndtasgtdt0(W4,xR,W6)
& ( W5 = W6
| ( ( aReductOfIn0(W6,W5,xR)
| ? [W7] :
( aElement0(W7)
& aReductOfIn0(W7,W5,xR)
& sdtmndtplgtdt0(W7,xR,W6) ) )
& sdtmndtplgtdt0(W5,xR,W6) ) )
& sdtmndtasgtdt0(W5,xR,W6) ) ) )
=> ? [W3] :
( aElement0(W3)
& ( W1 = W3
| aReductOfIn0(W3,W1,xR)
| ? [W4] :
( aElement0(W4)
& aReductOfIn0(W4,W1,xR)
& sdtmndtplgtdt0(W4,xR,W3) )
| sdtmndtplgtdt0(W1,xR,W3)
| sdtmndtasgtdt0(W1,xR,W3) )
& ( W2 = W3
| aReductOfIn0(W3,W2,xR)
| ? [W4] :
( aElement0(W4)
& aReductOfIn0(W4,W2,xR)
& sdtmndtplgtdt0(W4,xR,W3) )
| sdtmndtplgtdt0(W2,xR,W3)
| sdtmndtasgtdt0(W2,xR,W3) ) ) ) ) ).
%------------------------------------------------------------------------------