Syntactic semigroups of avoided languages
type: Item
instance of: scholarly article
title: Syntactic semigroups of avoided languages
zbMATH Open document ID: 0905.20037
DOI: 10.1007/BF02673917
published in: Siberian Mathematical Journal
publication date: 1998-11-22T00:00:00Z
review text: Let \(L\) and \(\Lambda\) be languages over alphabets \(A\) and \(\Sigma\), respectively. The author considers a language \(L\) of the shape ``\(L\) avoids \(\Lambda\)'', more presicely, the syntactic semigroup \(S_L\) of the language \(L\) of all binary strongly cube-free words. The main result is a solution of the word problem in \(S_L\); i.e., given an arbitrary pair of words in \(A\), decide whether they represent the same element of \(S_L\) (whether this pair belongs to the syntactic congruence of the language \(L\)).
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 1225836
zbMATH Keywords: syntactic semigroups
zbMATH Keywords: strongly cube-free words
zbMATH Keywords: words avoided by languages
zbMATH Keywords: syntactic congruences
zbMATH Keywords: word problem
author: Arseny M. Shur
MaRDI profile type: Publication
cites work: Avoidable patterns in strings of symbols
cites work: Q4508468
cites work: Binary words avoided by the Thue-Morse sequence
cites work: OVERLAP-FREE WORDS AND THUE-MORSE SEQUENCES
cites work: A Characterization of the Morse Minimal Set
description: scientific article; zbMATH DE number 1225836