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

      0 references
      1987
      0 references
      polynomial closure
      0 references
      class of languages
      0 references
      rational languages
      0 references
      concatenation hierarchy
      0 references
      decidable
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references