Séries formelles et algèbres syntactiques
Séries formelles et algèbres syntactiques
复制标题
形式与代数句法系列
DOI：
10.1016/0021-8693(80)90097-6
复制
发表时间：
1980
影响因子：
0.9
通讯作者：
Christophe Reutenauer
中科院分区：
文献类型：
--
作者：
Christophe Reutenauer
众所周知，句法幺半群的概念对于形式语言，特别是有理语言来说非常重要;这种重要性的例子是Kleene定理，Schützenberger关于非周期幺半群的定理和Eilenberg关于簇的定理。我们在这里介绍，对于形式幂级数，一个类似的对象：每一个形式幂级数，我们关联其语法代数。Kleene-Schützenberger定理可以这样表述：一个级数是有理的当且仅当它的句法代数有有限维。一个有理中心级数（这意味着一个词的系数只取决于它的共轭类）是字符的线性组合当且仅当它的句法代数是半单的。将一元有理级数的Fatou性质推广到多元级数，并对两个级数的Hadamard商的合理性的一种特殊情况作了肯定的回答。Eilenberg所研究的有限幺半群的伪簇与有理语言的伪簇之间的对应关系，在有限维代数的伪簇与有理级数的伪簇之间得到了扩展。我们研究了由闭包性质定义的不同种类的簇，并证明了一个类似于Schützenberger关于非周期幺半群的定理。
The notion of the syntactic monoid is well known to be very important for formal languages, and in particular for rational languages; examples of that importance are Kleene's theorem, Schützenberger's theorem about aperiodic monoid and Eilenberg's theorem about varieties. We introduce here, for formal power series, a similar object: to each formal power series we associate its syntactic algebra. The Kleene-Schützenberger theorem can then be stated in the following way: a series is rational if and only if its syntactic algebra has finite dimension. A rational central series (this means that the coefficient of a word depends only on its conjugacy class) is a linear combination of characters if and only if its syntactic algebra is semisimple. Fatou properties of rational series in one variable are extended to series in several variables and a special case of the rationality of the Hadamard quotient of two series is positively answered. The correspondence between pseudovarieties of finite monoids and varieties of rational languages, as studied by Eilenberg, is extended between pseudovarieties of finite dimensional algebras and varieties of rational series. We study different kinds of varieties that are defined by closure properties and prove a theorem similar to Schützenberger's theorem on aperiodic monoids.