TPTP Problem File: COM017+4.p
View Solutions
- Solve Problem
%------------------------------------------------------------------------------
% File : COM017+4 : TPTP v8.2.0. Released v4.0.0.
% Domain : Computing Theory
% Problem : Newman's lemma on rewriting systems 03_01_03, 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.03 [Pas08]
% Status : Theorem
% Rating : 0.22 v8.2.0, 0.19 v8.1.0, 0.25 v7.4.0, 0.13 v7.3.0, 0.14 v7.1.0, 0.13 v6.4.0, 0.15 v6.3.0, 0.25 v6.2.0, 0.28 v6.1.0, 0.40 v6.0.0, 0.39 v5.5.0, 0.41 v5.4.0, 0.50 v5.3.0, 0.52 v5.2.0, 0.25 v5.1.0, 0.38 v5.0.0, 0.50 v4.1.0, 0.61 v4.0.1, 0.78 v4.0.0
% Syntax : Number of formulae : 22 ( 1 unt; 6 def)
% Number of atoms : 191 ( 11 equ)
% Maximal formula atoms : 33 ( 8 avg)
% Number of connectives : 170 ( 1 ~; 34 |; 100 &)
% ( 6 <=>; 29 =>; 0 <=; 0 <~>)
% Maximal formula depth : 17 ( 8 avg)
% Maximal term depth : 1 ( 1 avg)
% Number of predicates : 12 ( 10 usr; 1 prp; 0-3 aty)
% Number of functors : 6 ( 6 usr; 6 con; 0-0 aty)
% Number of variables : 69 ( 48 !; 21 ?)
% 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__731,hypothesis,
( aElement0(xa)
& aElement0(xb)
& aElement0(xc) ) ).
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) ) )
=> ( iLess0(W0,xa)
=> ? [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__731_02,hypothesis,
( ( aReductOfIn0(xb,xa,xR)
| ? [W0] :
( aElement0(W0)
& aReductOfIn0(W0,xa,xR)
& sdtmndtplgtdt0(W0,xR,xb) ) )
& sdtmndtplgtdt0(xa,xR,xb)
& ( aReductOfIn0(xc,xa,xR)
| ? [W0] :
( aElement0(W0)
& aReductOfIn0(W0,xa,xR)
& sdtmndtplgtdt0(W0,xR,xc) ) )
& sdtmndtplgtdt0(xa,xR,xc) ) ).
fof(m__755,hypothesis,
( aElement0(xu)
& aReductOfIn0(xu,xa,xR)
& ( xu = xb
| ( ( aReductOfIn0(xb,xu,xR)
| ? [W0] :
( aElement0(W0)
& aReductOfIn0(W0,xu,xR)
& sdtmndtplgtdt0(W0,xR,xb) ) )
& sdtmndtplgtdt0(xu,xR,xb) ) )
& sdtmndtasgtdt0(xu,xR,xb) ) ).
fof(m__779,hypothesis,
( aElement0(xv)
& aReductOfIn0(xv,xa,xR)
& ( xv = xc
| ( ( aReductOfIn0(xc,xv,xR)
| ? [W0] :
( aElement0(W0)
& aReductOfIn0(W0,xv,xR)
& sdtmndtplgtdt0(W0,xR,xc) ) )
& sdtmndtplgtdt0(xv,xR,xc) ) )
& sdtmndtasgtdt0(xv,xR,xc) ) ).
fof(m__,conjecture,
? [W0] :
( aElement0(W0)
& ( xu = W0
| aReductOfIn0(W0,xu,xR)
| ? [W1] :
( aElement0(W1)
& aReductOfIn0(W1,xu,xR)
& sdtmndtplgtdt0(W1,xR,W0) )
| sdtmndtplgtdt0(xu,xR,W0)
| sdtmndtasgtdt0(xu,xR,W0) )
& ( xv = W0
| aReductOfIn0(W0,xv,xR)
| ? [W1] :
( aElement0(W1)
& aReductOfIn0(W1,xv,xR)
& sdtmndtplgtdt0(W1,xR,W0) )
| sdtmndtplgtdt0(xv,xR,W0)
| sdtmndtasgtdt0(xv,xR,W0) ) ) ).
%------------------------------------------------------------------------------