
doi: 10.1007/bfb0055073
In the seventies, several classification schemes for the rational languages were proposed, based on the alternate use of certain operators (union, complementation, product and star). Some thirty years later, although much progress has been done, several of the original problems are still open. Furthermore, their significance has grown considerably over the years, on account of the successive discoveries of surprising links with other fields, like non commutative algebra, finite model theory, structural complexity and topology. In this article, we solve positively a question raised in 1985 about concatenation hierarchies of rational languages, which are constructed by alternating boolean operations and concatenation products. We establish a simple algebraic connection between the Straubing-Thérien hierarchy, whose basis is the trivial variety, and the group hierarchy, whose basis is the variety of group languages. Thanks to a recent result of Almeida and Steinberg, this reduces the decidability problem for the group hierarchy to a property stronger than decidability for the Straubing-Thérien hierarchy.
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Concatenation hierarchy, variety of finite semigroups, regular language, [MATH.MATH-GR] Mathematics [math]/Group Theory [math.GR]
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Concatenation hierarchy, variety of finite semigroups, regular language, [MATH.MATH-GR] Mathematics [math]/Group Theory [math.GR]
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
