Reduction Techniques for Acyclic Cover Transducers

Article type: Research Article

Authors: Champarnaud, Jean-Marc | Farré, Jacques | Guingne, Franck

Affiliations: Laboratoire LITIS, Université de Rouen, France. [email protected] | Laboratoire I3S, Université de Nice - Sophia Antipolis & CNRS, France. [email protected] | Laboratoire I3S, Université de Nice - Sophia Antipolis & CNRS, France. [email protected]

Note: [] Address for correspondence: University of Rouen, LITIS, 76800 Saint-Etienne du Rouvray – France

Abstract: Finite languages and finite subsequential functions can be represented by possibly cyclic finite machines, respectively called cover automata and cover transducers. Reduced cover machines can have fewer states than the corresponding minimal machines, yielding a compact representation for lexicons or dictionaries. We present here a new algorithm for reducing the number of states of an acyclic transducer.

Keywords: Finite subsequential function, Acyclic transducer, Cover transducer

DOI: 10.3233/FI-2011-567

Journal: Fundamenta Informaticae, vol. 111, no. 4, pp. 357-371, 2011