scientific article; zbMATH DE number 4035179
[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.
- Polynomial operations and hierarchies of concatenation
- Polynomial closure and unambiguous product
- Algebraic tools for the concatenation product.
- Some complexity results for polynomial rational expressions.
- Characterizing level one in group-based concatenation hierarchies
- Geometrical closure of binary \(V_{3/2}\) languages
- Generic results for concatenation hierarchies
- Concatenation hierarchies: new bottle, old wine
- Languages of dot-depth 3/2
- Quantifier alternation for infinite words
- A Note on Decidable Separability by Piecewise Testable Languages
- Theme and variations on the concatenation product
- A conjecture on the concatenation product
- Polynomial languages with finite antidictionaries
- Equations Defining the Polynomial Closure of a Lattice of Regular Languages
- Polynomial Operators on Classes of Regular Languages
- Rational series and their languages
- Two non-closure results on families ofL languages
- Bridges for concatenation hierarchies
- Separating regular languages with two quantifier alternations
- The covering problem
- Polynomial closure and unambiguous product
- The globals of pseudovarieties of ordered semigroups containingB2and an application to a problem proposed by Pin
- Separating Without Any Ambiguity.
- Separation for dot-depth two
- An explicit formula for the intersection of two polynomials of regular languages
- How many times do you need to go back to the future in unary temporal logic?
- The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
- All about unambiguous polynomial closure
- The amazing mixed polynomial closure and its applications to two-variable first-order logic
- A generic characterization of generalized unary temporal logic and two-variable first-order logic
- Dot-depth three, return of the j-class
- On the complexity of computing the profinite closure of a rational language
- A purely algebraic proof of the omega-reducibility of pseudovarieties representing low half levels of concatenation hierarchies
- On the state complexity of closures and interiors of regular languages with subwords and superwords
- A note on partially ordered tree automata
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)