Abstract
Abstract: The single shortest path algorithm is undefined for weighted finite-state automata over non-idempotent semirings because such semirings do not guarantee the existence of a shortest path. However, in non-idempotent semirings admitting an order satisfying a monotonicity condition (such as the plus-times or log semirings), the shortest string is well-defined. We describe an algorithm which finds the shortest string for a weighted non-deterministic automaton over such semirings using the backwards shortest distance of an equivalent deterministic automaton (DFA) as a heuristic for A* search performed over a companion idempotent semiring, which is proven to return the shortest string. There may be exponentially more states in the DFA, but the proposed algorithm needs to visit only a small fraction of them if determinization is performed “on the fly”.- Anthology ID:
- 2024.eacl-long.43
- Volume:
- Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)
- Month:
- March
- Year:
- 2024
- Address:
- St. Julian’s, Malta
- Editors:
- Yvette Graham, Matthew Purver
- Venue:
- EACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 732–739
- Language:
- URL:
- https://aclanthology.org/2024.eacl-long.43
- DOI:
- Cite (ACL):
- Kyle Gorman and Cyril Allauzen. 2024. A* shortest string decoding for non-idempotent semirings. In Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pages 732–739, St. Julian’s, Malta. Association for Computational Linguistics.
- Cite (Informal):
- A* shortest string decoding for non-idempotent semirings (Gorman & Allauzen, EACL 2024)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-2/2024.eacl-long.43.pdf