New Results on the Generalized Star-Height Problem
New Results on the Generalized Star-Height Problem
复制标题
广义星高问题的新结果
DOI：
--
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
D. Thérien
中科院分区：
文献类型：
--
作者：
J. Pin;Howard Straubing;D. Thérien
证明了与广义星高问题有关的一些结果。在这个问题中，相对于限制星高问题，互补被认为是一个基本的操作。我们首先证明了星高n的语言类在某些运算下是封闭的（左、右同元，逆字母态射，内射无星替换）。已知交换群所识别的语言的星高为1。我们把这个结果推广到2类幂零群和交换群的半直积被（Z= 2 Z）n整除的群。在同样的方向上，我们表明，在过去的十年中，一种被证明是星星高度为2的语言，实际上是星星高度为1。接下来，我们表明，如果一个合理的语言L是由一个幺半群的形式M（G N），其中M和N是非周期幺半群的花环产品所产生的品种，G是一个交换群，那么L的星高1。最后，我们表明，每一个合理的语言是逆图像，在一些自由幺半群之间的态射，（限制）星高1的语言。确定一个理性语言的星高是形式语言理论的一个老问题（见Brzozowski [1]，历史回顾）。Hashiguchi [4]最近解决了限制星高问题，但在这里我们感兴趣的是关于广义星高问题的那一方面，其中互补被认为是基本算子。因此，在本文的其余部分，“星高”一词将始终指广义星高。本文的目的是提出一些新的结果有关的starheight问题：是否有一个算法来计算的star-height的一个给定的理性语言”（这种语言可以给出，例如，由一个理性表达式）。恒星高度的问题似乎是非常复杂的，关于这个问题我们所知甚少。例如，目前尚不清楚是否有
We prove some results related to the generalized star-height problem. In this problem, as opposed to the restricted star-height problem, complementation is considered as a basic operator. We rst show that the class of languages of star-height n is closed under certain operations (left and right quotients, inverse alphabetic morphisms, injective star-free substitutions). It is known that languages recognized by a commutative group are of star-height 1. We extend this result to nilpotent groups of class 2 and to the groups that divide a semidirect product of a commutative group by (Z=2Z) n . In the same direction, we show that one of the languages that was conjectured to be of star height 2 during the past ten years, is in fact of star height 1. Next we show that if a rational language L is recognized by a monoid of the variety generated by wreath products of the form M (G N), where M and N are aperiodic monoids, and G is a commutative group, then L is of star-height 1. Finally we show that every rational language is the inverse image, under some morphism between free monoids, of a language of (restricted) star-height 1. The determination of the star-height of a rational language is an old problem of formal language theory (see Brzozowski [1], for an historical survey). The restricted star-height problem has been recently solved by Hashiguchi [4], but here we are interested in that aspect of the problem concerning generalized starheight, in which complementation is considered as a basic operator. Thus, in the rest of this paper, the word "star-height" will always refer to generalized star-height. The aim of this paper is to present some new results related to the starheight problem : Is there an algorithm to compute the star-height of a given rational language" (this language can be given, for instance, by a rational expression). The star-height problem seems to be extremely dicult, and very little is known on the subject. For instance, it is not yet known whether there