Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl pre05627363
Cain, Alan J.
Monoids presented by rewriting systems and automatic structures for their submonoids. (English)
[J] Int. J. Algebra Comput. 19, No. 6, 771-790 (2009). ISSN 0218-1967

Summary: This paper studies $rr-$, $\ell r$-, $r\ell $-, and $\ell \ell $-automatic structures for finitely generated submonoids of monoids presented by confluent rewriting system that are either finite and special or regular and monadic. A new technique is developed that uses an automaton to "translate" between words in the original rewriting system and words over the generators for the submonoid. This is applied to show that the submonoid inherits any notion of automatism possessed by the original monoid. Generalizations of results of Otto and Ruškuc are thus obtained: every finitely generated submonoid of a monoid presented by a confluent finite special rewriting system admits an automatic structure that is simultaneously $rr-$, $\ell r$-, $r\ell $-, and $\ell \ell $-automatic; and every finitely generated submonoid of a monoid presented by a confluent regular monadic rewriting system admits an automatic structure that is simultaneously $rr$- and $\ell \ell $-automatic. These structures are shown to be effectively computable. An algorithm is given to decide whether the monoid presented by a confluent monadic finite rewriting system is $\ell r$- or $r\ell $-automatic. Finally, these results are applied to yield answers to some hitherto open questions and to recover and generalize established results.

MSC 2000:: *20M05 Free semigroups
68Q45 Formal languages

Keywords: automatic monoids; string rewriting systems; submonoids

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]