A tighter analysis of Piterman's Büchi determinization |
| |
Authors: | Wanwei Liu Ji Wang |
| |
Affiliation: | National Laboratory for Parallel and Distributed Processing, School of Computer Science, National University of Defense Technology, Changsha 410073, PR China |
| |
Abstract: | Determinization and complementation are two fundamental problems in automata theory. Very recently, Piterman improved Safra's determinization and, presented a new construction which produces parity automata with a smaller size. We give a tighter analysis on that determinization construction and show that the number of states of the resulting deterministic automaton is bounded by 2n2(n!) instead of 2n!nn. |
| |
Keywords: | Analysis of algorithms Formal languages Automata theory |
本文献已被 ScienceDirect 等数据库收录! |
|