TPTP Problem File: COM023+4.p
View Solutions
- Solve Problem
%------------------------------------------------------------------------------
% File : COM023+4 : TPTP v9.0.0. Released v4.0.0.
% Domain : Computing Theory
% Problem : Newman's lemma on rewriting systems 03_02, 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_02.03 [Pas08]
% Status : Theorem
% Rating : 0.30 v9.0.0, 0.31 v8.2.0, 0.28 v7.5.0, 0.25 v7.4.0, 0.13 v7.3.0, 0.14 v7.2.0, 0.10 v7.1.0, 0.13 v6.4.0, 0.19 v6.3.0, 0.25 v6.2.0, 0.24 v6.1.0, 0.33 v6.0.0, 0.39 v5.5.0, 0.44 v5.4.0, 0.50 v5.3.0, 0.48 v5.2.0, 0.25 v5.1.0, 0.33 v5.0.0, 0.42 v4.1.0, 0.48 v4.0.1, 0.74 v4.0.0
% Syntax : Number of formulae : 18 ( 1 unt; 6 def)
% Number of atoms : 177 ( 11 equ)
% Maximal formula atoms : 33 ( 9 avg)
% Number of connectives : 160 ( 1 ~; 33 |; 91 &)
% ( 6 <=>; 29 =>; 0 <=; 0 <~>)
% Maximal formula depth : 18 ( 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__715,hypothesis,
! [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] :
( 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) ) ) ).
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] :
( 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) ) ) )
| isConfluent0(xR) ) ).
%------------------------------------------------------------------------------