Extensions and submonoids of automatic monoids

• Type: Article in International Scientific Journal
• Date: 2002

Authors

Pedro V. Silva (Author) FCUP; Steinberg, B (Author) Other

Journal

Title: Theoretical Computer Science

Vol. 289

Pages: 727-754

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 12 Citations

Scopus - 12 Citations

Other information

Authenticus ID: P-000-MNM

DOI: 10.1016/s0304-3975(01)00390-5

Abstract (EN): In this paper, submonoids and extensions of automatic and p-automatic monoids are studied. The concept of a p-automatic monoid is a variant on the usual concept of an automatic monoid designed to allow a geometric characterization analogous to the group case. In the case of right cancellative monoids, the two concepts coincide. Here, we study rational submonoids of (p-)automatic monoids, being able to show in many cases that (p-)automaticity is inherited. Our sharpest results concern rational subgroups. Also, closure properties are established for various notions of extensions of (p-)automatic monoids, including different types of products, ideal extensions, and Rees matrix constructions.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 28