Skip to main content
SpringerLink
Log in

Finiteness and Regularity in Semigroups and Formal Languages

  • Book
  • © 1999

Overview

Authors:
  1. Aldo Luca

    1. Dipartimento di Matematica, Università di Roma „La Sapienza€, Roma, Italy

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Stefano Varricchio

    1. Dipartimento di Matematica, Università di Roma „Torvergata€, Roma, Italy

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Rigorous presentation of latest research results A unique and definitive monograph on a central subject in theoretical computer science with various applications
  • A must for all experts in theoretical computer science and combinatorics Self-contained account of new results on semigroups and formal languages
  • Includes supplementary material: sn.pub/extras

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

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (6 chapters)

  1. Front Matter

    Pages I-X
    Download chapter PDF

  2. Combinatorics on Words

    • Aldo de Luca, Stefano Varricchio
    Pages 1-30

  3. Unavoidable Regularities

    • Aldo de Luca, Stefano Varricchio
    Pages 31-76

  4. Finiteness Conditions for Semigroups

    • Aldo de Luca, Stefano Varricchio
    Pages 77-152

  5. Finitely Recognizable Semigroups

    • Aldo de Luca, Stefano Varricchio
    Pages 153-177

  6. Regularity Conditions

    • Aldo de Luca, Stefano Varricchio
    Pages 179-194

  7. Well Quasi-orders and Regularity

    • Aldo de Luca, Stefano Varricchio
    Pages 195-227

  8. Back Matter

    Pages 229-242
    Download chapter PDF
Back to top

Keywords

About this book

The aim of this monograph is to present some recent research work on the combinatorial aspects of the theory of semigroups which are of great inter­ est for both algebra and theoretical computer science. This research mainly concerns that part of combinatorics of finite and infinite words over a finite alphabet which is usually called the theory of "unavoidable" regularities. The unavoidable regularities ofsufficiently large words over a finite alpha­ bet are very important in the study of finiteness conditions for semigroups. This problem consists in considering conditions which are satisfied by a fi­ nite semigroup and are such as to assure that a semigroup satisfying them is finite. The most natural requirement is that the semigroup is finitely gener­ ated. Ifone supposes that the semigroup is also periodic the study offiniteness conditions for these semigroups (or groups) is called the Burnside problem for semigroups (or groups). There exists an important relationship with the theory of finite automata because, as is well known, a language L over a fi­ nite alphabet is regular (that is, recognizable by a finite automaton) if and only if its syntactic monoid S(L) is finite. Hence, in principle, any finite­ ness condition for semigroups can be translated into a regularity condition for languages. The study of finiteness conditions for periodic languages (Le. , such that the syntactic semigroup is periodic) has been called the Burnside problem for languages.

Authors and Affiliations

  • Dipartimento di Matematica, Università di Roma „La Sapienza€, Roma, Italy

    Aldo Luca

  • Dipartimento di Matematica, Università di Roma „Torvergata€, Roma, Italy

    Stefano Varricchio

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation