abstract.tex

% !TEX root = main.tex
%
% Symbolic Weighted (SW) extension of symbolic automata...
%
%\florent{revise following intro}
We study properties and relationship between three classes of
quantitative language models computing over infinite input alphabets:
%propose a framework for weighted parsing over infinite alphabets.
Symbolic Weighted Automata (\SWA)
at the joint between Symbolic Automata (\SA) and Weighted Automata (\WA),
as well as Transducers (\SWT) and Visibly Pushdown (\SWVPA) variants.
%
Like \SA, \SWA deal with large or infinite input alphabets,
and like \WA, they output a weight value in a semiring domain.
The transitions of \SWA are labeled by functions from an infinite alphabet into the weight domain.
This generalizes \SA, whose transitions are guarded by Boolean predicates
overs symbols in an infinite alphabet,
and also \WA, whose transitions are labeled by constant weight values,
and which deal only with finite alphabets.
%
We present a Bar-Hillel Perles Shamir construction of a \SWA
computing a \SWT-defined distance between a \SWA input language and a word, 
some closure results 
and a polynomial best-search algorithm for \SWVPA. 
These results are applied to solve a variant of parsing over infinite alphabets.
%
%We illustrate the model with a motivating application to
%automated music transcription.