Singular value automata and approximate minimization. (27th October 2019)
- Record Type:
- Journal Article
- Title:
- Singular value automata and approximate minimization. (27th October 2019)
- Main Title:
- Singular value automata and approximate minimization
- Authors:
- Balle, Borja
Panangaden, Prakash
Precup, Doina - Abstract:
- Abstract: The present paper uses spectral theory of linear operators to construct approximatelyminimal realizations of weighted languages. Our new contributions are: (i) a new algorithm for the singular value decomposition (SVD) decomposition of finite-rank infinite Hankel matrices based on their representation in terms of weighted automata, (ii) a new canonical form for weighted automata arising from the SVD of its corresponding Hankelmatrix, and (iii) an algorithmto construct approximateminimizations of given weighted automata by truncating the canonical form.We give bounds on the quality of our approximation.
- Is Part Of:
- Mathematical structures in computer science. Volume 29:Number 9(2020)
- Journal:
- Mathematical structures in computer science
- Issue:
- Volume 29:Number 9(2020)
- Issue Display:
- Volume 29, Issue 9 (2019)
- Year:
- 2019
- Volume:
- 29
- Issue:
- 9
- Issue Sort Value:
- 2019-0029-0009-0000
- Page Start:
- 1444
- Page End:
- 1478
- Publication Date:
- 2019-10-27
- Subjects:
- Computer science -- Mathematics -- Periodicals
004.015105 - Journal URLs:
- http://journals.cambridge.org/action/displayJournal?jid=MSC ↗
- DOI:
- 10.1017/S0960129519000094 ↗
- Languages:
- English
- ISSNs:
- 0960-1295
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library HMNTS - ELD Digital store
- Ingest File:
- 16588.xml