scientific article; zbMATH DE number 4035179

From MaRDI portal
Publication:3774976





[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.




Cited in
(36)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3774976)