[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Complexity of ideals in finite semigroups and finite-state machines

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

# G (S) denotes the complexity of a finite semigroup as introduced by Krohn and Rhodes. IfI is a maximal ideal or maximal left ideal of a semigroupS, then# G (I) ⩽ # G (S) ⩽ # G (I) + 1. Thus, ifV is an ideal ofS with# G (S) = n ⩾ k = # G (V), then there is a chain of ideals ofS

$$V = V_k \subset V_{k + 1} \subset ... \subset V_n \subseteq S$$

with# G (V j ) =j, i.e., complexity is continuous with respect to ideals.

Given a representation ofS as a subsemigroup ofF R (Q), all mappings on the setQ(e.g., as the semigroup of a finite state sequential machine with statesQ) a rank ideal consists of all elements ofS whose range contains no more thank elements for some fixed integerk. The above result also applies to rank ideals.

Existing results on complexity are reviewed in the language of finite-state sequential machines.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. H. Clifford andG. R. Preston,The Algebraic Theory of Semigroups, Vol. 1, Math. Surveys No. 7, Amer. Math. Soc., Providence, R.I., 1962.

    Google Scholar 

  2. J. Hartmanis andR. E. Stearns,Algebraic Structure Theory of Sequential Machines, Prentice-Hall, Inc., 1966.

  3. Kenneth Krohn, Richard Mateosian andJohn Rhodes, “Methods of the Algebraic Theory of Machines, I,”Journal of Computer and Systems Sciences (to appear).

  4. K. B. Krohn andJ. L. Rhodes, “Algebraic Theory of Machines,” Polytechnic Institute of Brooklyn,Proceedings of the Symposium on Mathematical Theory of Automata, J. Fox (ed.), pp. 341–384 (1963).

  5. —, Algebraic theory of machines. I. Prime decomposition theorem for finite semi-groups and machines,Trans. Amer. Math. Soc. 116 (1965), 450–464.

    Google Scholar 

  6. -, Complexity of finite semigroups, (submitted toAnn. of Math.).

  7. -, “Complexity of Finite Semigroups and Finite State Machines, The General Case,” to appear in theProceedings of the Conference on Algebraic Theory of Machines, Languages and Semigroups, 1966.

  8. —, Results on finite semigroups derived from the algebraic theory of machines,Proc. Nat. Acad. Sci. U.S.A. 53 (1965), 499–501.

    Google Scholar 

  9. John Rhodes, “Complexity and characters of finite semigroups,” (submitted toJ. Algebra).

  10. -, Some results on finite semigroups,J. Algebra (to appear).

  11. H. P. Zeiger, Cascade synthesis of finite-state machines,Information and Control (to appear).

  12. J. A. Green, On the structure of semigroups,Ann. of Math. 54 (1951), 163–172.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Krohn-Rhodes Research Institute, 610 23rd. Street, Washington, D.C., USA

    Kenneth Krohn

  2. University of California, Berkeley, USA

    Richard Mateosian

  3. Krohn-Rhodes Research Institute, 1472 A University Avenue, Berkeley, California, USA

    John Rhodes

  4. Institute for Advanced Study, Princeton, New Jersey, USA

    John Rhodes

  5. University of California, Berkeley, USA

    John Rhodes

Authors
  1. Kenneth Krohn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Richard Mateosian
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. John Rhodes
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported by the United States Air Force, Air Force Systems Command, Systems Engineering Group, Wright-Patterson AFB, Ohio, under Contract Number: AF 33(615)-3893.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Krohn, K., Mateosian, R. & Rhodes, J. Complexity of ideals in finite semigroups and finite-state machines. Math. Systems Theory 1, 59–66 (1967). https://doi.org/10.1007/BF01692497

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01692497

Keywords

Search

Navigation