Simpler and more general minimization for weighted finite-state automata

@inproceedings{citeulike:2137663, abstract = {Previous work on minimizing weighted finite-state automata (including transducers) is limited to particular types of weights. We present efficient new minimization algorithms that apply much more generally, while being simpler and about as fast.We also point out theoretical limits on minimization algorithms. We characterize the kind of "well-behaved" weight semirings where our methods work. Outside these semirings, minimization is not well-defined (in the sense of producing a unique minimal automaton), and even finding the minimum number of states is in general NP-complete and inapproximable.}, address = {Morristown, NJ, USA}, author = {Eisner, Jason }, booktitle = {NAACL '03: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology}, citeulike-article-id = {2137663}, doi = {10.3115/1073445.1073454}, keywords = {algorithms, automata}, pages = {64--71}, posted-at = {2007-12-17 17:32:00}, priority = {2}, publisher = {Association for Computational Linguistics}, title = {Simpler and more general minimization for weighted finite-state automata}, url = {http://portal.acm.org/citation.cfm?id=1073454}, year = {2003} }

TY - CONF ID - citeulike:2137663 L3 - citeulike-article-id:2137663 TI - Simpler and more general minimization for weighted finite-state automata T2 - NAACL '03: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology SP - 64 EP - 71 AD - Morristown, NJ, USA PB - Association for Computational Linguistics N2 - Previous work on minimizing weighted finite-state automata (including transducers) is limited to particular types of weights. We present efficient new minimization algorithms that apply much more generally, while being simpler and about as fast.We also point out theoretical limits on minimization algorithms. We characterize the kind of "well-behaved" weight semirings where our methods work. Outside these semirings, minimization is not well-defined (in the sense of producing a unique minimal automaton), and even finding the minimum number of states is in general NP-complete and inapproximable. KW - algorithms KW - automata AU - Eisner, Jason PY - 2003/// UR - http://portal.acm.org/citation.cfm?id=1073454 ER -