On the starheight of some rational subsets closed under partial commutations
type: Item
instance of: scholarly article
title: On the starheight of some rational subsets closed under partial commutations
zbMATH Open document ID: 0789.68082
author: Christian Choffrut
published in: Information and Computation
publication date: 1994-06-13T00:00:00Z
review text: For a partial commutation relation (a symmetric partial relation) \(\theta\subseteq A\times A\), over an alphabet \(A\), we denote by \(\bar\theta\) its complement: for a string \(w\in A^*\), denote by \([w^*]\) the set of all words in \(A^*\) equivalent to a power \(w^ n\) of \(w\) under the partial commutation \(\theta\). This set is a regular language if and only if \(\bar\theta\) as a graph on the vertices \(A\) is connected [\textit{R. Cori} and \textit{D. Perrin}, RAIRO, Inf. Theor. Appl.19, 21-32 (1985; Zbl 0601.68055)]. The present paper investigates the starheight of languages of the form \([w^*]\) for \(\theta\) as above with \(\bar\theta\) connected. It is proved that (1) when \(\theta\) is not connected, then the starheight is one, but (2) when \(\theta\) is connected, then the starheight can be arbitrarily large: for each \(n>0\) there exists \(w\in A^*\) of length \(O(n)\) such that \([w^*]\) has the starheight equal to \(n\). This second result is a stronger form of a theorem (presented without a complete proof) by \textit{C. Choffrut} and \textit{C. Duboc} [Lect. Notes Comput. Sci. 267, 190-201 (1987; Zbl 0634.20026)].
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 465564
zbMATH Keywords: free monoids
zbMATH Keywords: rational set
zbMATH Keywords: partial commutation relation
zbMATH Keywords: regular language
zbMATH Keywords: starheight of languages
reviewed by: Gheorghe Păun
MaRDI profile type: Publication
full work available at URL: inco.1993.1049
OpenAlex ID: W1990586430
DOI: 10.1006/INCO.1993.1049
description: scientific article; zbMATH DE number 465564