Tool CaT
stdout:
YES(?,O(n^1))
Problem:
0(q0(0(x1))) -> 0(0(q0(x1)))
0(q0(1(x1))) -> 0(1(q0(x1)))
1(q0(0(x1))) -> 0(0(q1(x1)))
1(q0(1(x1))) -> 0(1(q1(x1)))
1(q1(0(x1))) -> 1(0(q1(x1)))
1(q1(1(x1))) -> 1(1(q1(x1)))
0(q1(0(x1))) -> 0(0(q2(x1)))
0(q1(1(x1))) -> 0(1(q2(x1)))
1(q2(0(x1))) -> 1(0(q2(x1)))
1(q2(1(x1))) -> 1(1(q2(x1)))
0(q2(x1)) -> q3(1(x1))
1(q3(x1)) -> q3(1(x1))
0(q3(x1)) -> q4(0(x1))
1(q4(x1)) -> q4(1(x1))
0(q4(0(x1))) -> 1(0(q5(x1)))
0(q4(1(x1))) -> 1(1(q5(x1)))
1(q5(0(x1))) -> 0(0(q1(x1)))
1(q5(1(x1))) -> 0(1(q1(x1)))
0(q5(x1)) -> q6(0(x1))
1(q6(x1)) -> q6(1(x1))
1(q7(0(x1))) -> 0(0(q8(x1)))
1(q7(1(x1))) -> 0(1(q8(x1)))
0(q8(x1)) -> 0(q0(x1))
1(q8(0(x1))) -> 1(0(q8(x1)))
1(q8(1(x1))) -> 1(1(q8(x1)))
0(q6(x1)) -> q9(0(x1))
0(q9(0(x1))) -> 1(0(q7(x1)))
0(q9(1(x1))) -> 1(1(q7(x1)))
1(q9(x1)) -> q9(1(x1))
h(q0(x1)) -> h(0(q0(x1)))
q0(h(x1)) -> q0(0(h(x1)))
h(q1(x1)) -> h(0(q1(x1)))
q1(h(x1)) -> q1(0(h(x1)))
h(q2(x1)) -> h(0(q2(x1)))
q2(h(x1)) -> q2(0(h(x1)))
h(q3(x1)) -> h(0(q3(x1)))
q3(h(x1)) -> q3(0(h(x1)))
h(q4(x1)) -> h(0(q4(x1)))
q4(h(x1)) -> q4(0(h(x1)))
h(q5(x1)) -> h(0(q5(x1)))
q5(h(x1)) -> q5(0(h(x1)))
h(q6(x1)) -> h(0(q6(x1)))
q6(h(x1)) -> q6(0(h(x1)))
Proof:
Bounds Processor:
bound: 1
enrichment: match
automaton:
final states: {13,12,11,10,9,8,7,6,5,4}
transitions:
q91(29) -> 30*
11(36) -> 37*
11(38) -> 39*
11(28) -> 29*
01(18) -> 19*
q01(20) -> 21*
q01(17) -> 18*
q01(26) -> 27*
00(2) -> 4*
00(1) -> 4*
00(3) -> 4*
q00(2) -> 7*
q00(1) -> 7*
q00(3) -> 7*
10(2) -> 5*
10(1) -> 5*
10(3) -> 5*
q10(2) -> 8*
q10(1) -> 8*
q10(3) -> 8*
q20(2) -> 9*
q20(1) -> 9*
q20(3) -> 9*
q30(2) -> 10*
q30(1) -> 10*
q30(3) -> 10*
q40(2) -> 11*
q40(1) -> 11*
q40(3) -> 11*
q50(2) -> 12*
q50(1) -> 12*
q50(3) -> 12*
q60(2) -> 13*
q60(1) -> 13*
q60(3) -> 13*
q70(2) -> 1*
q70(1) -> 1*
q70(3) -> 1*
q80(2) -> 2*
q80(1) -> 2*
q80(3) -> 2*
q90(2) -> 3*
q90(1) -> 3*
q90(3) -> 3*
h0(2) -> 6*
h0(1) -> 6*
h0(3) -> 6*
1 -> 36,20
2 -> 28,17
3 -> 38,26
19 -> 4*
21 -> 18*
27 -> 18*
30 -> 39,29,5
37 -> 29*
39 -> 29*
problem:
QedTool IRC1
stdout:
MAYBE
Tool IRC2
stdout:
YES(?,O(n^1))
'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost runtime-complexity with respect to
Rules:
{ 0(q0(0(x1))) -> 0(0(q0(x1)))
, 0(q0(1(x1))) -> 0(1(q0(x1)))
, 1(q0(0(x1))) -> 0(0(q1(x1)))
, 1(q0(1(x1))) -> 0(1(q1(x1)))
, 1(q1(0(x1))) -> 1(0(q1(x1)))
, 1(q1(1(x1))) -> 1(1(q1(x1)))
, 0(q1(0(x1))) -> 0(0(q2(x1)))
, 0(q1(1(x1))) -> 0(1(q2(x1)))
, 1(q2(0(x1))) -> 1(0(q2(x1)))
, 1(q2(1(x1))) -> 1(1(q2(x1)))
, 0(q2(x1)) -> q3(1(x1))
, 1(q3(x1)) -> q3(1(x1))
, 0(q3(x1)) -> q4(0(x1))
, 1(q4(x1)) -> q4(1(x1))
, 0(q4(0(x1))) -> 1(0(q5(x1)))
, 0(q4(1(x1))) -> 1(1(q5(x1)))
, 1(q5(0(x1))) -> 0(0(q1(x1)))
, 1(q5(1(x1))) -> 0(1(q1(x1)))
, 0(q5(x1)) -> q6(0(x1))
, 1(q6(x1)) -> q6(1(x1))
, 1(q7(0(x1))) -> 0(0(q8(x1)))
, 1(q7(1(x1))) -> 0(1(q8(x1)))
, 0(q8(x1)) -> 0(q0(x1))
, 1(q8(0(x1))) -> 1(0(q8(x1)))
, 1(q8(1(x1))) -> 1(1(q8(x1)))
, 0(q6(x1)) -> q9(0(x1))
, 0(q9(0(x1))) -> 1(0(q7(x1)))
, 0(q9(1(x1))) -> 1(1(q7(x1)))
, 1(q9(x1)) -> q9(1(x1))
, h(q0(x1)) -> h(0(q0(x1)))
, q0(h(x1)) -> q0(0(h(x1)))
, h(q1(x1)) -> h(0(q1(x1)))
, q1(h(x1)) -> q1(0(h(x1)))
, h(q2(x1)) -> h(0(q2(x1)))
, q2(h(x1)) -> q2(0(h(x1)))
, h(q3(x1)) -> h(0(q3(x1)))
, q3(h(x1)) -> q3(0(h(x1)))
, h(q4(x1)) -> h(0(q4(x1)))
, q4(h(x1)) -> q4(0(h(x1)))
, h(q5(x1)) -> h(0(q5(x1)))
, q5(h(x1)) -> q5(0(h(x1)))
, h(q6(x1)) -> h(0(q6(x1)))
, q6(h(x1)) -> q6(0(h(x1)))}
Proof Output:
'Bounds with minimal-enrichment and initial automaton 'match'' proved the best result:
Details:
--------
'Bounds with minimal-enrichment and initial automaton 'match'' succeeded with the following output:
'Bounds with minimal-enrichment and initial automaton 'match''
--------------------------------------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost runtime-complexity with respect to
Rules:
{ 0(q0(0(x1))) -> 0(0(q0(x1)))
, 0(q0(1(x1))) -> 0(1(q0(x1)))
, 1(q0(0(x1))) -> 0(0(q1(x1)))
, 1(q0(1(x1))) -> 0(1(q1(x1)))
, 1(q1(0(x1))) -> 1(0(q1(x1)))
, 1(q1(1(x1))) -> 1(1(q1(x1)))
, 0(q1(0(x1))) -> 0(0(q2(x1)))
, 0(q1(1(x1))) -> 0(1(q2(x1)))
, 1(q2(0(x1))) -> 1(0(q2(x1)))
, 1(q2(1(x1))) -> 1(1(q2(x1)))
, 0(q2(x1)) -> q3(1(x1))
, 1(q3(x1)) -> q3(1(x1))
, 0(q3(x1)) -> q4(0(x1))
, 1(q4(x1)) -> q4(1(x1))
, 0(q4(0(x1))) -> 1(0(q5(x1)))
, 0(q4(1(x1))) -> 1(1(q5(x1)))
, 1(q5(0(x1))) -> 0(0(q1(x1)))
, 1(q5(1(x1))) -> 0(1(q1(x1)))
, 0(q5(x1)) -> q6(0(x1))
, 1(q6(x1)) -> q6(1(x1))
, 1(q7(0(x1))) -> 0(0(q8(x1)))
, 1(q7(1(x1))) -> 0(1(q8(x1)))
, 0(q8(x1)) -> 0(q0(x1))
, 1(q8(0(x1))) -> 1(0(q8(x1)))
, 1(q8(1(x1))) -> 1(1(q8(x1)))
, 0(q6(x1)) -> q9(0(x1))
, 0(q9(0(x1))) -> 1(0(q7(x1)))
, 0(q9(1(x1))) -> 1(1(q7(x1)))
, 1(q9(x1)) -> q9(1(x1))
, h(q0(x1)) -> h(0(q0(x1)))
, q0(h(x1)) -> q0(0(h(x1)))
, h(q1(x1)) -> h(0(q1(x1)))
, q1(h(x1)) -> q1(0(h(x1)))
, h(q2(x1)) -> h(0(q2(x1)))
, q2(h(x1)) -> q2(0(h(x1)))
, h(q3(x1)) -> h(0(q3(x1)))
, q3(h(x1)) -> q3(0(h(x1)))
, h(q4(x1)) -> h(0(q4(x1)))
, q4(h(x1)) -> q4(0(h(x1)))
, h(q5(x1)) -> h(0(q5(x1)))
, q5(h(x1)) -> q5(0(h(x1)))
, h(q6(x1)) -> h(0(q6(x1)))
, q6(h(x1)) -> q6(0(h(x1)))}
Proof Output:
The problem is match-bounded by 1.
The enriched problem is compatible with the following automaton:
{ 0_0(2) -> 1
, 0_1(3) -> 1
, q0_0(2) -> 1
, q0_1(2) -> 3
, 1_0(2) -> 1
, 1_1(2) -> 4
, q1_0(2) -> 1
, q2_0(2) -> 1
, q3_0(2) -> 1
, q4_0(2) -> 1
, q5_0(2) -> 1
, q6_0(2) -> 1
, q7_0(2) -> 2
, q8_0(2) -> 2
, q9_0(2) -> 2
, q9_1(4) -> 1
, q9_1(4) -> 4
, h_0(2) -> 1}Tool RC1
stdout:
MAYBE
Tool RC2
stdout:
YES(?,O(n^1))
'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer: YES(?,O(n^1))
Input Problem: runtime-complexity with respect to
Rules:
{ 0(q0(0(x1))) -> 0(0(q0(x1)))
, 0(q0(1(x1))) -> 0(1(q0(x1)))
, 1(q0(0(x1))) -> 0(0(q1(x1)))
, 1(q0(1(x1))) -> 0(1(q1(x1)))
, 1(q1(0(x1))) -> 1(0(q1(x1)))
, 1(q1(1(x1))) -> 1(1(q1(x1)))
, 0(q1(0(x1))) -> 0(0(q2(x1)))
, 0(q1(1(x1))) -> 0(1(q2(x1)))
, 1(q2(0(x1))) -> 1(0(q2(x1)))
, 1(q2(1(x1))) -> 1(1(q2(x1)))
, 0(q2(x1)) -> q3(1(x1))
, 1(q3(x1)) -> q3(1(x1))
, 0(q3(x1)) -> q4(0(x1))
, 1(q4(x1)) -> q4(1(x1))
, 0(q4(0(x1))) -> 1(0(q5(x1)))
, 0(q4(1(x1))) -> 1(1(q5(x1)))
, 1(q5(0(x1))) -> 0(0(q1(x1)))
, 1(q5(1(x1))) -> 0(1(q1(x1)))
, 0(q5(x1)) -> q6(0(x1))
, 1(q6(x1)) -> q6(1(x1))
, 1(q7(0(x1))) -> 0(0(q8(x1)))
, 1(q7(1(x1))) -> 0(1(q8(x1)))
, 0(q8(x1)) -> 0(q0(x1))
, 1(q8(0(x1))) -> 1(0(q8(x1)))
, 1(q8(1(x1))) -> 1(1(q8(x1)))
, 0(q6(x1)) -> q9(0(x1))
, 0(q9(0(x1))) -> 1(0(q7(x1)))
, 0(q9(1(x1))) -> 1(1(q7(x1)))
, 1(q9(x1)) -> q9(1(x1))
, h(q0(x1)) -> h(0(q0(x1)))
, q0(h(x1)) -> q0(0(h(x1)))
, h(q1(x1)) -> h(0(q1(x1)))
, q1(h(x1)) -> q1(0(h(x1)))
, h(q2(x1)) -> h(0(q2(x1)))
, q2(h(x1)) -> q2(0(h(x1)))
, h(q3(x1)) -> h(0(q3(x1)))
, q3(h(x1)) -> q3(0(h(x1)))
, h(q4(x1)) -> h(0(q4(x1)))
, q4(h(x1)) -> q4(0(h(x1)))
, h(q5(x1)) -> h(0(q5(x1)))
, q5(h(x1)) -> q5(0(h(x1)))
, h(q6(x1)) -> h(0(q6(x1)))
, q6(h(x1)) -> q6(0(h(x1)))}
Proof Output:
'Bounds with minimal-enrichment and initial automaton 'match'' proved the best result:
Details:
--------
'Bounds with minimal-enrichment and initial automaton 'match'' succeeded with the following output:
'Bounds with minimal-enrichment and initial automaton 'match''
--------------------------------------------------------------
Answer: YES(?,O(n^1))
Input Problem: runtime-complexity with respect to
Rules:
{ 0(q0(0(x1))) -> 0(0(q0(x1)))
, 0(q0(1(x1))) -> 0(1(q0(x1)))
, 1(q0(0(x1))) -> 0(0(q1(x1)))
, 1(q0(1(x1))) -> 0(1(q1(x1)))
, 1(q1(0(x1))) -> 1(0(q1(x1)))
, 1(q1(1(x1))) -> 1(1(q1(x1)))
, 0(q1(0(x1))) -> 0(0(q2(x1)))
, 0(q1(1(x1))) -> 0(1(q2(x1)))
, 1(q2(0(x1))) -> 1(0(q2(x1)))
, 1(q2(1(x1))) -> 1(1(q2(x1)))
, 0(q2(x1)) -> q3(1(x1))
, 1(q3(x1)) -> q3(1(x1))
, 0(q3(x1)) -> q4(0(x1))
, 1(q4(x1)) -> q4(1(x1))
, 0(q4(0(x1))) -> 1(0(q5(x1)))
, 0(q4(1(x1))) -> 1(1(q5(x1)))
, 1(q5(0(x1))) -> 0(0(q1(x1)))
, 1(q5(1(x1))) -> 0(1(q1(x1)))
, 0(q5(x1)) -> q6(0(x1))
, 1(q6(x1)) -> q6(1(x1))
, 1(q7(0(x1))) -> 0(0(q8(x1)))
, 1(q7(1(x1))) -> 0(1(q8(x1)))
, 0(q8(x1)) -> 0(q0(x1))
, 1(q8(0(x1))) -> 1(0(q8(x1)))
, 1(q8(1(x1))) -> 1(1(q8(x1)))
, 0(q6(x1)) -> q9(0(x1))
, 0(q9(0(x1))) -> 1(0(q7(x1)))
, 0(q9(1(x1))) -> 1(1(q7(x1)))
, 1(q9(x1)) -> q9(1(x1))
, h(q0(x1)) -> h(0(q0(x1)))
, q0(h(x1)) -> q0(0(h(x1)))
, h(q1(x1)) -> h(0(q1(x1)))
, q1(h(x1)) -> q1(0(h(x1)))
, h(q2(x1)) -> h(0(q2(x1)))
, q2(h(x1)) -> q2(0(h(x1)))
, h(q3(x1)) -> h(0(q3(x1)))
, q3(h(x1)) -> q3(0(h(x1)))
, h(q4(x1)) -> h(0(q4(x1)))
, q4(h(x1)) -> q4(0(h(x1)))
, h(q5(x1)) -> h(0(q5(x1)))
, q5(h(x1)) -> q5(0(h(x1)))
, h(q6(x1)) -> h(0(q6(x1)))
, q6(h(x1)) -> q6(0(h(x1)))}
Proof Output:
The problem is match-bounded by 1.
The enriched problem is compatible with the following automaton:
{ 0_0(2) -> 1
, 0_1(3) -> 1
, q0_0(2) -> 1
, q0_1(2) -> 3
, 1_0(2) -> 1
, 1_1(2) -> 4
, q1_0(2) -> 1
, q2_0(2) -> 1
, q3_0(2) -> 1
, q4_0(2) -> 1
, q5_0(2) -> 1
, q6_0(2) -> 1
, q7_0(2) -> 2
, q8_0(2) -> 2
, q9_0(2) -> 2
, q9_1(4) -> 1
, q9_1(4) -> 4
, h_0(2) -> 1}