No label defined (Q3774976)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4035179
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4035179 |
Statements
1987
0 references
polynomial closure
0 references
class of languages
0 references
rational languages
0 references
concatenation hierarchy
0 references
decidable
0 references
0.9245826601982116
0 references
0.9201460480690002
0 references
0.8780649900436401
0 references
0.8332628011703491
0 references
0.8090949654579163
0 references
[For the entire collection see Zbl 0604.00016.] Given a class \({\mathcal C}\) of languages, let Pol(\({\mathcal C})\) be the polynomial closure of \({\mathcal C}\), that is, the smallest class of languages containing \({\mathcal C}\) and closed under the operations union and marked product L a L', where a is a letter. We determine the polynomial closure of various classes of rational languages and we study the properties of polynomial closures. For instance, if \({\mathcal C}\) is closed under quotients (resp. quotients and inverse morphism) then Pol(\({\mathcal C})\) has the same property. Our main result shows that if \({\mathcal C}\) is a Boolean algebra closed under quotients then Pol(\({\mathcal C})\) is closed under intersection. As an application, we refine the concatenation hierarchy introduced by Straubing and we show that the levels 1/2 and 3/2 of this hierarchy are decidable.
0 references