Büchi Determinization

NO.	States	Transitions	Letters	Acceptable States	File(.gff)
1	3	11	4	1
2	4	24	6	1
3	5	40	8	1
4	6	60	10	1
5	7	84	12	1

NO.	States	Transitions	Letters	Acceptable States	File(.gff)
1	10	26	2	2
2	10	30	2	3
3	10	26	2	3
4	10	32	2	5
5	10	23	2	2
6	10	36	2	3
7	10	32	2	4
8	10	28	2	1
9	10	37	2	2
10	10	32	2	3
11	20	102	2	4
12	20	82	2	5
13	20	94	2	4
14	20	95	2	2
15	20	102	2	3
16	20	74	2	3
17	20	55	2	6
18	20	88	2	8
19	20	60	2	5
20	20	64	2	1
21	30	123	2	1
22	30	115	2	5
23	30	103	2	6
24	30	126	2	12
25	30	129	2	11
26	30	180	2	5
27	30	134	2	6
28	30	96	2	7
29	30	155	2	8
30	30	128	2	6
31	40	178	2	6
32	40	227	2	7
33	40	236	2	9
34	40	163	2	12
35	40	200	2	6
36	40	167	2	4
37	40	147	2	15
38	40	167	2	8
39	40	191	2	6
40	40	215	2	11
41	50	251	2	4
42	50	235	2	11
43	50	190	2	6
44	50	227	2	18
45	50	240	2	19
46	50	237	2	18
47	50	295	2	21
48	50	198	2	6
49	50	198	2	1
50	50	203	2	2
51	60	294	2	1
52	60	372	2	5
53	60	260	2	6
54	60	240	2	7
55	60	367	2	16
56	60	381	2	9
57	60	545	2	11
58	60	264	2	4
59	60	369	2	5
60	60	554	2	14
61	70	344	2	17
62	70	336	2	12
63	70	523	2	10
64	70	428	2	19
65	70	270	2	11
66	70	353	2	7
67	70	552	2	13
68	70	735	2	12
69	70	411	2	20
70	70	363	2	10
71	80	427	2	9
72	80	389	2	10
73	80	409	2	25
74	80	670	2	16
75	80	366	2	12
76	80	702	2	10
77	80	453	2	15
78	80	906	2	18
79	80	1285	2	30
80	80	342	2	41
81	90	458	2	51
82	90	435	2	9
83	90	622	2	10
84	90	573	2	7
85	90	479	2	20
86	90	559	2	1
87	90	457	2	3
88	90	898	2	13
89	90	430	2	11
90	90	1643	2	27
91	100	1540	2	30
92	100	1105	2	28
93	100	700	2	16
94	100	615	2	26
95	100	569	2	15
96	100	454	2	20
97	100	461	2	24
98	100	614	2	27
99	100	599	2	4
100	100	543	2	7

Note: We suggest using Chrome browser. When the automata are large, due to the limitation of response time, the figures cannot be displayed on line. In this case, we suggest creating .DOT files of the automata and then show them with Gravix.

	0%

Result:

Input:	Result:


output

Experiment Results

We have implemented our determinization constructions, and compared the DRA (respectively DPA) transforms with these constructed by Schewe's (respectively Piterman's) algorithm.

NBA-TO-DPA

Benchmark 1: 100 NBA randomly generated with between 10 to 100 states (NBA used for NBA2DPA displayed in this web page).

Fig. 1 Comparing NBA-To-DPA Transforms on Benchmark 1

Note: The size is the sum of the numbers of states and transitions.

Benchmark 2: 11000 NBA (used to compare NBA complementation constructions originally. We get these from http://goal.im.ntu.edu.tw/) with an alphabet of size 2 and a state set of size 15 (A15), and 20 (A20), respectively. (Download Benchmark 2)

Table 1 Comparing NBA-To-DPA Transforms on Benchmark 2

#T.O.: the number of NBA which are not successfully determinized within 10 mins.
To < Tp: the percentage of NBA for which the constructions in our approach consumes less time than Piterman's.

NBA-TO-DRA

When comparing our approach with Schewe's, we find that the respective DRA transforms are the same for most of Benchmark 1 and 2. This is because most of these NBA have small alphabets. So, we perform another set of experiments.

Benchmark 3: 5 NBA with larger alphabets (NBA used for NBA2DRA displayed in this web page).

Table 2 Comparing NBA-To-DRA Transforms on Benchmark 3

#S:states #T:transitions #L:letters #I:indices
T.O.: fail to accomplish the transformation within 20 mins.