TRS Standard pair #615297096

details

property	value
status	complete
benchmark	payet-nonloop-2.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n021.star.cs.uiowa.edu
space	payet_21

run statistics

property	value
solver	AutoNon 1.21
configuration	autonon
runtime (wallclock)	207.567937136 seconds
cpu usage	809.681586593
max memory	1.9344273408E10

stage attributes

key	value
output-size	8712
starexec-result	"NO"

output

/export/starexec/sandbox2/solver/bin/starexec_run_autonon /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


NO

<html>
<body>
<pre style="font-family: monospace, serif; font-size: 1em; white-space: pre-wrap; margin: 20px; padding: 20px;">

*** AutoNon ***


AutoNon proves looping and non-looping non-termination using regular languages.

AutoNon employs SAT solving to find finite automata as certificates of non-termination.
The automata define (a) the language and (b) which rule may be applied where in a term.
By property (b), the language of the automaton does not need to be closed under rewriting.
It suffices that every term in the language admits some rewrite step to a term in the language.
Finally, we employ a quasi-order on the states of the automaton. This allows rewriting to
change the interpretation of a term (the state of the automaton) and thereby to change what
rules may be applied (the allowed rules depend on the state of the automaton).

The technique is described in the following paper:

    [EZ2015] Proving Non-Termination by Finite Automata
             by J. Endrullis and H. Zantema
             Proc. Conf. on Rewriting Techniques and Applications (RTA 2015)

For further information see <a href="http://joerg.endrullis.de/nonterm/">

       http://joerg.endrullis.de/nonterm/       

</a>

*** Input system ***

    f(0,Y,g(Z),U) -> f(s(Y),s(Y),g(1),U)
    f(s(X),Y,Z,s(U)) -> f(X,Y,Z,s(2))



*** Non-looping non-termination using regular languages ***


Input system R is not terminating since R admits a regular language weakly closed under rewriting.


The following finite automaton witnesses non-termination:

  The states are: 0,1,...,6

  The accepting states are: 6

  We use the following order < on the states:

        <  0  1  2  3  4  5  6
        0  1                  
        1     1               
        2        1            
        3           1         
        4              1      
        5                 1   
        6                    1

  The states determine the rules that may be used:

      state 0:
          f__1(f__2(f__3(0,Y),g(Z)),U) -> f__1(f__2(f__3(s(Y),s(Y)),g(1)),U)
          f__1(f__2(f__3(s(X),Y),Z),s(U)) -> f__1(f__2(f__3(X,Y),Z),s(2))
      state 1:
          f__1(f__2(f__3(0,Y),g(Z)),U) -> f__1(f__2(f__3(s(Y),s(Y)),g(1)),U)
          f__1(f__2(f__3(s(X),Y),Z),s(U)) -> f__1(f__2(f__3(X,Y),Z),s(2))
      state 2:
          f__1(f__2(f__3(0,Y),g(Z)),U) -> f__1(f__2(f__3(s(Y),s(Y)),g(1)),U)
          f__1(f__2(f__3(s(X),Y),Z),s(U)) -> f__1(f__2(f__3(X,Y),Z),s(2))
      state 3:
          f__1(f__2(f__3(0,Y),g(Z)),U) -> f__1(f__2(f__3(s(Y),s(Y)),g(1)),U)
          f__1(f__2(f__3(s(X),Y),Z),s(U)) -> f__1(f__2(f__3(X,Y),Z),s(2))
      state 4:
          f__1(f__2(f__3(0,Y),g(Z)),U) -> f__1(f__2(f__3(s(Y),s(Y)),g(1)),U)
          f__1(f__2(f__3(s(X),Y),Z),s(U)) -> f__1(f__2(f__3(X,Y),Z),s(2))
      state 5:
          f__1(f__2(f__3(0,Y),g(Z)),U) -> f__1(f__2(f__3(s(Y),s(Y)),g(1)),U)
          f__1(f__2(f__3(s(X),Y),Z),s(U)) -> f__1(f__2(f__3(X,Y),Z),s(2))
      state 6:
          f__1(f__2(f__3(0,Y),g(Z)),U) -> f__1(f__2(f__3(s(Y),s(Y)),g(1)),U)
          f__1(f__2(f__3(s(X),Y),Z),s(U)) -> f__1(f__2(f__3(X,Y),Z),s(2))

  Transitions for `f__3':

       x0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  2  2  2  2  2  2  2  3  3  3  3  3  3  3  4  4  4  4  4  4  4  5  5  5  5  5  5  5  6  6  6  6  6  6  6
       x1  0  1  2  3  4  5  6  0  1  2  3  4  5  6  0  1  2  3  4  5  6  0  1  2  3  4  5  6  0  1  2  3  4  5  6  0  1  2  3  4  5  6  0  1  2  3  4  5  6
      out
        0                                                                                                                                                   
        1                                                                                                                                                   
        2                                                                                                                                                   
        3

popout

output may be truncated. 'popout' for the full output.

job log

popout

actions all output return to TRS Standard