No label defined (Q4026901)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 125208
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 125208

      Statements

      21 February 1993
      0 references
      inverse monoids
      0 references
      free monoid
      0 references
      free inverse monoid
      0 references
      rooted tree
      0 references
      rational
      0 references
      recognizable
      0 references
      finitely generated
      0 references
      relations
      0 references
      idempotents
      0 references
      congruence
      0 references
      word problem
      0 references
      deterministic context-free language
      0 references
      0 references
      0 references
      [For the entire collection see Zbl 0745.00034.] There are announced some results concerning the theory of inverse monoids. The proofs are absent. Let \(X\) be a set and \(X^{-1}\) a set disjoint from \(X\) and in one-to-one correspondence with \(X\) by a map \(x \mapsto x^{-1}\). Let \(\rho\) be the smallest congruence on the free monoid \((X \cup X^{-1})^*\) such that the laws \(x = xx^{-1}x\), \((x^{-1})^{-1} = x\), \(x^{-1} xy^{-1} y = y^{-1} yx^{-1} x\) hold in \((X \cup X^{-1})^*/\rho\). Then the monoid \((X \cup X^{- 1})^*/\rho\) is called the free inverse monoid on \(X\) and is denoted by \(\text{FIM}(X)\). A subset \(T\) of an inverse semigroup \(S\) is called closed if \(a \in T\), \(b \in S\) and \(b\geq a\) implies \(b \in T\). Let \(T\) be a rooted tree and a group \(G\) act freely on \(T\) on the left. Then we can build a semigroup \(P(G,T)\) which is isomorphic to a closed inverse submonoid of a free inverse monoid \(\text{FIM}(X)\) on some set \(X\). Conversely, every closed submonoid of a free inverse monoid is isomorphic to some semigroup \(P(G,T)\) built in this way. It is proved that for a closed inverse submonoid \(M\) of the free inverse monoid \(\text{FIM}(X)\) the following conditions are equivalent: (1) \(M\) is finitely generated; (2) \(M\) has finite index; (3) \(M\) is rational; (4) \(M\) is recognizable. The condition (5) gives a topological characterization for a finitely generated closed inverse submonoid \(M\). Let \(M\) be an inverse monoid generated by a set \(X\) and a finite set \(T = \{e_ i = f_ i \mid i \in I\}\) of defining relations \(e_ i = f_ i\), where \(e_ i\) and \(f_ i\) are idempotents of \(\text{FIM}(X)\). Let \(\tau\) be a congruence on \(\text{FIM}(X)\) generated by the set \(T\). Then the word problem in \(M\) is decidable, and the set of the form \(u \uparrow = \{w \in (X \cup X^{- 1})^*\): \(w \tau \geq u\tau\) in \(M\}\) is a deterministic context-free language. There are some other results.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references