On the word problem for syntactic monoids of piecewise testable languages.
type: Item
instance of: scholarly article
title: On the word problem for syntactic monoids of piecewise testable languages.
zbMATH Open document ID: 1261.20075
author: Kamilla Kátai-Urbán
author: Péter Pál Pach
author: Gabriella Pluhár
author: András Pongrácz
author: Csaba Szabó
published in: Semigroup Forum
publication date: 2012-08-16T00:00:00Z
review text: The word \(w\) is a \textit{subword} of \(u\) if \(w\) is a subsequence of not necessary consecutive variables taken from \(u\). Given a natural number \(k\) let \(u\sim_kv\) if and only if the words \(u,v\) over the alphabet \(X\) have the same set of subwords of length at most \(k\). A language \(L\) over the alphabet \(X\) is \textit{\(k\)-piecewise testable} if and only if \(L\) is the union of classes of the equivalence relation \(\sim_k\). \textit{I. Simon} [Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)] found a basis of identities for the variety of finite monoids corresponding to a class of \(k\)-piecewise testable languages if \(k=1,2\). \textit{F. Blanchet-Sadri} gave a basis of identities for \(k=3\), and proved that there is no finite basis of identities for \(k>3\) [see Theor. Comput. Sci. 123, No. 2, 239-258 (1994; Zbl 0801.68105)]. In this paper a normal form is presented for the varieties of finite monoids corresponding to a class of \(k\)-piecewise testable languages for \(k=2,3\) and a log-asypmtotic estimate is given for the number of words over these monoids.
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 6066635
zbMATH Keywords: semigroups
zbMATH Keywords: piecewise testable languages
zbMATH Keywords: pseudovarieties of finite monoids
zbMATH Keywords: free syntactic monoids
zbMATH Keywords: word problem
zbMATH Keywords: bases of identities
zbMATH Keywords: normal form theorems
MaRDI profile type: Publication
full work available at URL: s00233-011-9357-z
OpenAlex ID: W2054241966
cites work: Games, equations and the dot-depth hierarchy
cites work: Equations and monoid varieties of dot-depth one and two
cites work: Q3123631
cites work: Q3769981
cites work: Complexity of some problems from the theory of automata
cites work: Q4077455
DOI: 10.1007/S00233-011-9357-Z
description: scientific article; zbMATH DE number 6066635