Reduction Techniques for Acyclic Cover Transducers

• Autorzy: Champarnaud, J-M. , Farré, J. , Guingne, F.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

finite subsequential function; acyclic transducer; cover transducer

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 4
• Strony: 357-371
• Opis fizyczny: Bibliogr. 18 poz., tab., wykr.

Twórcy

autor

Champarnaud, J-M.

autor

Farré, J.

autor

Guingne, F.

• University of Rouen, LITIS, 76800 Saint-Etienne du Rouvray – France,

Bibliografia

• [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
• [2] M.-P. Béal and O. Carton. Computing the prefix of an automaton. RAIRO Theoret. Informatics Appl., 34(6):503-514, 2000. IGM Report 2000-08.
• [3] J. Berstel. Transductions and Context-Free Languages, volume 38 of Leitfäden der angewandtenMathematik und Mechanik LAMM. Teubner, 1979.
• [4] C. Câmpeanu, A. Pǎun, and S. Yu. An efficient algorithm for constructing minimal cover automata for finite languages. Int. J. Found. Comput. Sci., 13(1):83-97, 2002.
• [5] C. Câmpeanu, N. Sântean, and S. Yu. Minimal cover-automata for finite languages. In WIA '98, volume 1660 of Lecture Notes in Computer Science, pages 43-56. Springer-Verlag, 1998.
• [6] C. Câmpeanu, N. Sântean, and S. Yu. Minimal cover-automata for finite languages. Theor. Comput. Sci., 267(1-2):3-16, September 2001.
• [7] J.-M. Champarnaud, F. Guingne, and J. Farré. Reducing acyclic cover transducers. In Jan Holub and Jan Zdárek, editors, CIAA, volume 4783 of Lecture Notes in Computer Science, pages 38-50. Springer, 2007.
• [8] J.-M. Champarnaud, F. Guingne, and G. Hansel. Cover transducers for functions with finite domain. Int. J. Found. Comput. Sci., 16(5):851-865, 2005.
• [9] J.-M. Champarnaud, F. Guingne, and G. Hansel. Similarity relations and cover automata. RAIRO Theoret. Informatics Appl., 39(1):115-123, January 2005.
• [10] Ch. Choffrut. Contribution `a l'étude de quelques familles remarquables de fonctions rationnelles. Thèse d'état, Université Paris 7, 1978. Mathématiques.
• [11] Ch. Choffrut. Minimizing subsequential transducers: a survey. Theor. Comput. Sci., 292(1):131-143, January 2003.
• [12] C. Dwork and L. Stockmeyer. A time complexity gap for two-way probabilistic finite-state automata. SIAMJC, 19:1011-1023, 1990.
• [13] J. Kaneps and R. Freivalds. Running time to recognize nonregular languages by 2-way probabilistic automata. In J. Leach Albert, B. Monien, and M. Rodr´ıguez Artalejo, editors, ICALP91, volume 510 of Lecture Notes in Computer Science, pages 174-185. Springer Verlag, 1991.
• [14] H. Körner. A time and space efficient algorithm for minimizing cover automata for finite languages. Int. J. Found. Comput. Sci., 14(6):1071-1086,December 2003.
• [15] M. Mohri. Minimization algorithms for sequential transducers. Theor. Comput. Sci., 234(1-2):177-201, March 2000.
• [16] R. Paige and R. Endre Tarjan. Three partition refinement algorithms. SIAMJ. Comput., 16(6):973-989, 1987.
• [17] A. Pǎun, N. Sântean, and S. Yu. An O(n2) algorithm for constructing minimal cover automata for finite languages. In A. Pǎun and S. Yu, editors, CIAA2000, volume 2088 of Lecture Notes in Computer Science, pages 243-251. Springer Verlag, 2001.
• [18] M.-P. Schützenberger. Sur une variante des fonctions séquentielles. Theor. Comput. Sci., 4(1):47-57, 1977