The Krohn-Rhodes Theorem and Local Divisors

• Autorzy: Diekert V. , Kufleitner M. , Steinberg B.
• Języki publikacji: EN

Abstrakty

EN

We give a new proof of the Krohn-Rhodes theorem using local divisors. The proof provides nearly as good a decomposition in terms of size as the holonomy decomposition of Eilenberg, avoids induction on the size of the state set, and works exclusively with monoids with the base case of the induction being that of a group.

Słowa kluczowe

EN

automaton; decomposition; monoid; transformation monoid; wreath product

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 65--77
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Diekert V.

autor

Kufleitner M.

autor

Steinberg B.

• Institut für Formale Methoden der Informatik Universit¨at Stuttgart, Stuttgart, Germany,

Bibliografia

• [1] Clifford, A. H., Preston, G. B.: The algebraic theory of semigroups, vol. 1,2, AmericanMathematical Society, 1961,1967.
• [2] Cohen, R. S., Brzozowski, J. A.: On star-free events, in: Proc. Hawaii Int. Conf. on System Science (B. K. Kinariwala, F. F. Kuo, Eds.), University of Hawaii Press, Honolulu, HI, 1968, 1-4.
• [3] Diekert, V., Gastin, P.: Pure future local temporal logics are expressively complete for Mazurkiewicz traces, Information and Computation, 204, 2006, 1597-1619, Conference version in LATIN 2004, LNCS 2976, 170-182, 2004.
• [4] Diekert, V., Gastin, P.: First-order definable languages, in: Logic and Automata: History and Perspectives, Texts in Logic and Games, Amsterdam University Press, 2008, 261-306.
• [5] Eilenberg, S.: Automata, Languages, and Machines, vol. B, Academic Press, New York and London, 1976.
• [6] ésik, Z.: A proof of the Krohn-Rhodes Decomposition Theorem, Theor. Comput. Sci., 234(1-2), 2000, 287-300.
• [7] Fernández López, A., Tocón Barroso,M.: The local algebras of an associative algebra and their applications, Applicable Mathematics in the Golden Age (J. Misra, Ed.), Narosa, 2002.
• [8] Ginzburg, A.: Algebraic theory of automata, ACM monograph series, Academic Press, 1968.
• [9] Holcombe,W.M. L.: Algebraic Automata Theory, Cambridge Studies in AdvancedMathematics, Cambridge University Press, 1982.
• [10] Krohn, K., Rhodes, J.: Algebraic theory of machines. I: Prime decomposition theorem for finite semigroups and machines., Transactions of the American Mathematical Society, 116, 1965, 450-464.
• [11] Krohn, K., Rhodes, J. L., Tilson, B.: The Prime Decomposition Theorem of the Algebraic Theory of Machines, in: Algebraic Theory of Machines, Languages, and Semigroups (M. A. Arbib, Ed.), chapter 5, Academic Press, New York and London, 1968, 81-125.
• [12] Lallement, G.: On the prime decomposition theorem for finite monoids, Math. Systems Theory, 5, 1971, 8-12.
• [13] Lallement, G.: Augmentations and wreath products of monoids, Semigroup Forum, 21(1), 1980, 89-90.
• [14] Meyberg, K.: Lectures on algebras and triple systems, Technical report, University of Virginia, Charlottesville, 1972.
• [15] Meyer, A. R.: A note on star-free events, J. Assoc. Comput. Mach., 16, 1969, 220-225.
• [16] Meyer, A. R., Thompson, C.: Remarks on Algebraic Decomposition of Automata, Mathematical Systems Theory, 3(2), 1969, 110-118.
• [17] Rhodes, J.: Applications of automata theory and algebra, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2010, Via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. With an editorial preface by Chrystopher L. Nehaniv and a foreword by Morris W. Hirsch.
• [18] Rhodes, J., Steinberg, B.: The q-theory of finite semigroups., SpringerMonographs inMathematics, Springer, 2009.
• [19] Schützenberger, M. P.: On finite monoids having only trivial subgroups, Information and Control, 8, 1965, 190-194.
• [20] Straubing, H.: Families of recognizable sets corresponding to certain varieties of finite monoids, Journal of Pure and Applied Algebra, 15, 1979, 305-318.
• [21] Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, Boston, Basel and Berlin, 1994.
• [22] Zeiger, P.: Yet another proof of the cascade decomposition theorem for finite automata, Math. Systems Theory, 1(3), 1967, 225-228.