𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on decidability questions on presentations of word semigroups

✍ Scribed by C. Choffrut; T. Harju; J. Karhumäki

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
665 KB
Volume
183
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We apply automata-theoretic tools and some recently established compactness properties in the study of F-semigroups, that is, subsemigroups of free semigroups. With each F-semigroup we associate an F-presentation, which turns out to be finite for all finitely generated F-semigroups.

Connections between F-presentations and ordinary presentations of semigroups are pointed out. It is also shown that it is undecidable whether two finitely generated F-semigroups satisfy a common relation in their F-presentations.

📜 SIMILAR VOLUMES

A note on the decidability of exponentia
A note on the decidability of exponential terms
✍ Paola D'Aquino; Giuseppina Terzo 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract In this paper we prove, modulo Schanuel's Conjecture, that there are algorithms which decide if two exponential polynomials in π are equal in ℝ and if two exponential polynomials in π and __i__ coincide in ℂ. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)