Finiteness and Regularity in Semigroups and Formal Languages

Finiteness and Regularity in Semigroups and Formal Languages by Aldo de Luca, Stefano Varricchio.

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 fin...

Full description

Saved in:
Bibliographic Details
Main Authors: Luca, Aldo de (Author), Varricchio, Stefano (Author)
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1999.
Edition:1st ed. 1999.
Series:Monographs in Theoretical Computer Science. An EATCS Series,
Springer eBook Collection.
Subjects:
Computer logic.
Software engineering.
Computer science—Mathematics.
Data structures (Computer science).
Algebra.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • 1. Combinatorics on Words
  • 1.1 Preliminaries
  • 1.2 Infinite words
  • 1.3 Metric and topology
  • 1.4 Periodicity and conjugacy
  • 1.5 Lyndon words
  • 1.6 Factorial languages and subword complexity
  • 2. Unavoidable Regularities
  • 2.1 Ramsey’s theorem
  • 2.2 Van der Waerden’s theorem
  • 2.3 Uniformly recurrent words
  • 2.4 Shirshov’s theorem
  • 2.5 Bounded languages
  • 2.6 Power-free words
  • 2.7 Bi-ideal sequences
  • 3. Finiteness Conditions for Semigroups
  • 3.1 Preliminaries on semigroups
  • 3.2 Finitely generated semigroups
  • 3.3 The Burnside problem
  • 3.4 Permutation property
  • 3.5 Partial commutations
  • 3.6 Chain conditions
  • 3.7 Iteration property
  • 3.8 Permutation and iteration property
  • 3.9 Repetitivity
  • 4. Finitely Recognizable Semigroups
  • 4.1 The Myhill-Nerode theorem
  • 4.2 Finitely recognizable semigroups
  • 4.3 The factor semigroup
  • 4.4 Rewriting systems
  • 4.5 The word problem
  • 4.6 On a conjecture of Brzozowski
  • 4.7 On a conjecture of Brown
  • 5. Regularity Conditions
  • 5.1 Uniform conditions
  • 5.2 Pumping properties
  • 5.3 Permutative property
  • 6. Well Quasi-orders and Regularity
  • 6.1 Well quasi-orders
  • 6.2 Higman’s theorem
  • 6.3 The generalized Myhill theorem
  • 6.4 Quasi-orders and rewriting systems
  • 6.5 A regularity condition for permutable languages
  • 6.6 Almost-commutative languages
  • 6.7 Copying systems
  • References.

Similar Items