We study several classes of symbolic weighted formalisms: automata (swA), transducers (swT) and visibly pushdown extensions (swVPA, swVPT). They combine the respective extensions of their symbolic and weighted counterparts, allowing a quantitative evaluation of words over a large or infinite input alphabet.
We present properties of closure by composition, the computation of transducer-defined distances between nested words and languages, as well as a PTIME 1-best search algorithm for swVPA. These results are applied to solve in PTIME a variant of parsing over infinite alphabets. We illustrate this approach with a motivating use case in automated music transcription.
Symbolic Weighted Language Models, Quantitative Parsing and Automated Music Transcription
Florent Jacquemard and Lydia Rodriguez-de la Nava
26th International Conference on Implementation and Application of Automata (CIAA’22), Rouen France
- link to the paper: https://hal.archives-ouvertes.fr/hal-03647675
- DOI: 10.1007/978-3-031-07469-1_5 (Springer LNCS)
- slides of the presentation: CIAA22-FJLRdLN
