×

Direct and dual laws for automata with multiplicities. (English) Zbl 0984.68098

Summary: We present here theoretical results coming from the implementation of the package called AMULT (Automata with MULTiplicities). We show that classical formulas are optimal for the bounds. Especially they are almost everywhere optimal for the fields \(R\) and \(C.\) We characterize the dual laws preserving rationality and examine compatibility between the geometry of the \(K\)-automata and these laws.

MSC:

68Q45 Formal languages and automata

Software:

Grail; AMoRE; AUTOMATE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Andary, P. Caron, J.-M. Champarnaud, G. Duchamp, M. Flouret, É. Laugerotte, SEA: a symbolic environement for automata, Proc. WIA’99, Postdam, 1999.; P. Andary, P. Caron, J.-M. Champarnaud, G. Duchamp, M. Flouret, É. Laugerotte, SEA: a symbolic environement for automata, Proc. WIA’99, Postdam, 1999. · Zbl 1050.68587
[2] Berstel, J.; Reutenauer, C., Rational Series and Their Languages (1988), Springer: Springer Berlin · Zbl 0668.68005
[3] Champarnaud, J.-M.; Hansel, G., Automate, a computing package for automata and finite semigroups, J. Symbolic Comput., 12, 197-220 (1991) · Zbl 0804.68096
[4] Culik, K.; Kari, J., (Finite state transformations of images, Proc. ICALP 95, Lecture Notes in Computer Science, Vol. 944 (1995), Springer: Springer Berlin), 51-62 · Zbl 1412.68125
[5] Duchamp, G.; Reutenauer, C., Un critère de rationalité provenant de la géométrie noncommutative, Invent. Math., 128, 613-622 (1997) · Zbl 0870.68093
[6] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[7] Fliess, M., Matrices de Hankel, J. Math. Pures Appl., 53, 197-224 (1974) · Zbl 0315.94051
[8] Fliess, M., Sur divers produits de séries formelles, Bull. Sc. Math., 102, 181-191 (1974) · Zbl 0313.13021
[9] M. Flouret, Contribution à l’algorithmique noncommutative, Ph.D. Thesis, Université de Rouen, 1999.; M. Flouret, Contribution à l’algorithmique noncommutative, Ph.D. Thesis, Université de Rouen, 1999.
[10] Flouret, M.; Laugerotte, É., Noncommutative minimization algorithms, Inform. Process. Lett., 64, 123-126 (1997) · Zbl 1337.68173
[11] Gaubert, S.; Mairesse, J., Modeling and analysis of timed Petri nets using heap of pieces, IEEE, Trans. Automat. Control, 44, 4, 683-697 (1999) · Zbl 0955.68082
[12] Harju, T.; Karhumäki, J., The equivalence problem of multitape finite automata, Theoret. Comput. Sci., 78, 347-355 (1991) · Zbl 0727.68063
[13] Hopcroft, J.; Ullman, D., Introduction to Automata Theory Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[14] S.C. Kleene, Representation of Events in Nerve Nets and Finite Automata, in: C.E. Shannon, J. McCarthy (Eds.), Automata Studies, Princeton, Univ. Press, Princeton, NJ, 1954, Study 34, pp. 3-41.; S.C. Kleene, Representation of Events in Nerve Nets and Finite Automata, in: C.E. Shannon, J. McCarthy (Eds.), Automata Studies, Princeton, Univ. Press, Princeton, NJ, 1954, Study 34, pp. 3-41.
[15] Kuich, W.; Salomaa, A., Semirings, Automata, Languages (1986), Springer: Springer Berlin
[16] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[17] J.G. Luque, Monoı̈des et automates admettant un produit de mélange, Ph.D. Thesis, Université de Rouen, 1999.; J.G. Luque, Monoı̈des et automates admettant un produit de mélange, Ph.D. Thesis, Université de Rouen, 1999.
[18] O. Matz, A. Miller, A. Potthoff, W. Thomas, E. Valkena, Report on the Program AMore, Technical Report, Institut für Informatik und Praktische Mathematik, Christian-Albrechts Universität, Kiel, 1995.; O. Matz, A. Miller, A. Potthoff, W. Thomas, E. Valkena, Report on the Program AMore, Technical Report, Institut für Informatik und Praktische Mathematik, Christian-Albrechts Universität, Kiel, 1995.
[19] Mazurkiewicz, A., (Traces, Histories and Graph: Instances of a Process Monoid, Lecture Notes in Computer Science, Vol. 176 (1984), Springer: Springer Berlin), 115-133
[20] H.N. Minh, G. Jacob, N. Oussous, Input/output behaviour of non-linear control systems: rational approximations, nilpotent and structural approximations, Analysis of controlled dynamical systems, in: Gauthier, Bonnar, Bride, Kupta (Eds.), Progress and Control Theory, Birkhauser, Bessel, 1991, pp. 253-262.; H.N. Minh, G. Jacob, N. Oussous, Input/output behaviour of non-linear control systems: rational approximations, nilpotent and structural approximations, Analysis of controlled dynamical systems, in: Gauthier, Bonnar, Bride, Kupta (Eds.), Progress and Control Theory, Birkhauser, Bessel, 1991, pp. 253-262. · Zbl 0789.93066
[21] Mohri, M.; Pereira, F.; Riley, M., A rational design for a weighted finite-state transducer library, Proc. WIA’97, 43-53 (1997)
[22] P. Ochsenschläger, Binomialkoeffitzenten und Shuffle-Zahlen, Technischer Bericht, Fachbereich Informatik, T.H. Darmstadt, 1981.; P. Ochsenschläger, Binomialkoeffitzenten und Shuffle-Zahlen, Technischer Bericht, Fachbereich Informatik, T.H. Darmstadt, 1981.
[23] Raymond, D. R.; Wood, D., GrailA C++ library for automata and expressions, J. Symbolic Comput., 17, 341-350 (1994) · Zbl 0942.68803
[24] Salomaa, A.; Soittola, M., Automata-Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
[25] Schützenberger, M. P., On the definition of a family of automata, Inform. and Control, 4, 245-270 (1961) · Zbl 0104.00702
[26] Schützenberger, M. P., On a theorem of R. Jungen, Proc. Amer. Soc., 13, 885-890 (1962) · Zbl 0107.03102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.