TPTP Problem File: COM020+1.p
View Solutions
- Solve Problem
%------------------------------------------------------------------------------
% File : COM020+1 : TPTP v8.2.0. Released v4.0.0.
% Domain : Computing Theory
% Problem : Newman's lemma on rewriting systems 03_01_05_01, 00 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_05_01.00 [Pas08]
% Status : Theorem
% Rating : 0.25 v8.2.0, 0.28 v8.1.0, 0.25 v7.5.0, 0.31 v7.4.0, 0.23 v7.3.0, 0.21 v7.1.0, 0.13 v7.0.0, 0.17 v6.4.0, 0.23 v6.3.0, 0.25 v6.2.0, 0.32 v6.1.0, 0.40 v6.0.0, 0.35 v5.5.0, 0.33 v5.4.0, 0.36 v5.3.0, 0.41 v5.2.0, 0.25 v5.1.0, 0.38 v5.0.0, 0.46 v4.1.0, 0.52 v4.0.1, 0.74 v4.0.0
% Syntax : Number of formulae : 24 ( 2 unt; 6 def)
% Number of atoms : 111 ( 1 equ)
% Maximal formula atoms : 10 ( 4 avg)
% Number of connectives : 88 ( 1 ~; 2 |; 53 &)
% ( 6 <=>; 26 =>; 0 <=; 0 <~>)
% Maximal formula depth : 12 ( 6 avg)
% Maximal term depth : 1 ( 1 avg)
% Number of predicates : 12 ( 10 usr; 1 prp; 0-3 aty)
% Number of functors : 8 ( 8 usr; 8 con; 0-0 aty)
% Number of variables : 50 ( 43 !; 7 ?)
% 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,
( isLocallyConfluent0(xR)
& isTerminating0(xR) ) ).
fof(m__731,hypothesis,
( aElement0(xa)
& aElement0(xb)
& aElement0(xc) ) ).
fof(m__715,hypothesis,
! [W0,W1,W2] :
( ( aElement0(W0)
& aElement0(W1)
& aElement0(W2)
& sdtmndtasgtdt0(W0,xR,W1)
& sdtmndtasgtdt0(W0,xR,W2) )
=> ( iLess0(W0,xa)
=> ? [W3] :
( aElement0(W3)
& sdtmndtasgtdt0(W1,xR,W3)
& sdtmndtasgtdt0(W2,xR,W3) ) ) ) ).
fof(m__731_02,hypothesis,
( sdtmndtplgtdt0(xa,xR,xb)
& sdtmndtplgtdt0(xa,xR,xc) ) ).
fof(m__755,hypothesis,
( aElement0(xu)
& aReductOfIn0(xu,xa,xR)
& sdtmndtasgtdt0(xu,xR,xb) ) ).
fof(m__779,hypothesis,
( aElement0(xv)
& aReductOfIn0(xv,xa,xR)
& sdtmndtasgtdt0(xv,xR,xc) ) ).
fof(m__799,hypothesis,
( aElement0(xw)
& sdtmndtasgtdt0(xu,xR,xw)
& sdtmndtasgtdt0(xv,xR,xw) ) ).
fof(m__818,hypothesis,
aNormalFormOfIn0(xd,xw,xR) ).
fof(m__,conjecture,
? [W0] :
( aElement0(W0)
& sdtmndtasgtdt0(xb,xR,W0)
& sdtmndtasgtdt0(xd,xR,W0) ) ).
%------------------------------------------------------------------------------