Monographs in Theoretical Computer Science. An EATCS Series

Finiteness and Regularity in Semigroups and Formal Languages

Authors: Luca, Aldo de, Varricchio, Stefano

  • 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

Buy this book

eBook $119.00
price for USA (gross)
  • ISBN 978-3-642-59849-4
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $159.00
price for USA
  • ISBN 978-3-642-64150-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
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.

Table of contents (6 chapters)

Buy this book

eBook $119.00
price for USA (gross)
  • ISBN 978-3-642-59849-4
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $159.00
price for USA
  • ISBN 978-3-642-64150-3
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Finiteness and Regularity in Semigroups and Formal Languages
Authors
Series Title
Monographs in Theoretical Computer Science. An EATCS Series
Copyright
1999
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag Berlin Heidelberg
eBook ISBN
978-3-642-59849-4
DOI
10.1007/978-3-642-59849-4
Softcover ISBN
978-3-642-64150-3
Series ISSN
1431-2654
Edition Number
1
Number of Pages
X, 240
Topics