Details

Autor(en) / Beteiligte

• Karlov, B

Titel

Algorithmic properties of some fragments of concatenation theory

Ist Teil von

• Journal of physics. Conference series, 2021-05, Vol.1902 (1), p.12117

Ort / Verlag

Bristol: IOP Publishing

Erscheinungsjahr

2021

Link zum Volltext

Quelle

EZB Electronic Journals Library

Beschreibungen/Notizen

• Abstract The paper considers two fragments of the word theory with concatenation. The first fragment has two relations denoting that one of the words is a prefix (respectively, a suffix) of another one. It is proved that this theory is algorithmically equivalent to elementary arithmetic and, therefore, undecidable. The second fragment has a countable set of power operations. It is proved that this theory admits effective quantifier elimination and is, therefore, decidable.