Abstract
Let \(\mathcal{L}\) be a set of regular languages of A *. An \(\mathcal{L}\)-polynomial is a finite union of products of the form L 0 a 1 L 1 ⋯ a n L n , where each a i is a letter of A and each L i is a language of \(\mathcal{L}\). We give an explicit formula for computing the intersection of two \(\mathcal{L}\)-polynomials. Contrary to Arfi’s formula (1991) for the same purpose, our formula does not use complementation and only requires union, intersection and quotients. Our result also implies that if \(\mathcal{L}\) is closed under union, intersection and quotient, then its polynomial closure, its unambiguous polynomial closure and its left [right] deterministic polynomial closure are closed under the same operations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arfi, M.: Opérations polynomiales et hiérarchies de concaténation. Theoret. Comput. Sci. 91, 71–84 (1991)
Branco, M.J.J.: On the Pin-Thérien expansion of idempotent monoids. Semigroup Forum 49(3), 329–334 (1994)
Branco, M.J.J.: The kernel category and variants of the concatenation product. Internat. J. Algebra Comput. 7(4), 487–509 (1997)
Branco, M.J.J.: Two algebraic approaches to variants of the concatenation product. Theoret. Comput. Sci. 369(1-3), 406–426 (2006)
Branco, M.J.J.: Deterministic concatenation product of languages recognized by finite idempotent monoids. Semigroup Forum 74(3), 379–409 (2007)
Branco, M.J.J., Pin, J.-É.: Equations defining the polynomial closure of a lattice of regular languages. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 115–126. Springer, Heidelberg (2009)
Lothaire, M.: Combinatorics on words, Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997)
Perrin, D., Pin, J.-E.: Infinite Words. Pure and Applied Mathematics, vol. 141, Elsevier (2004) ISBN 0-12-532111-2
Pin, J.-E.: Propriétés syntactiques du produit non ambigu. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 483–499. Springer, Heidelberg (1980)
Pin, J.-E.: A variety theorem without complementation. Russian Mathematics (Iz. VUZ) 39, 80–90 (1995)
Pin, J.-E., Straubing, H., Thérien, D.: Locally trivial categories and unambiguous concatenation. J. of Pure and Applied Algebra 52, 297–311 (1988)
Pin, J.-E., Thérien, D.: The bideterministic concatenation product. Internat. J. Algebra Comput. 3, 535–555 (1993)
Pin, J.-E., Weil, P.: Polynomial closure and unambiguous product. Theory Comput. Systems 30, 1–39 (1997)
Schützenberger, M.-P.: Une théorie algébrique du codage, in Séminaire Dubreil-Pisot, année 1955-56, Exposé No. 15, 27 février 1956, 24 pages, Inst. H. Poincaré, Paris (1956)
Schützenberger, M.-P.: Sur le produit de concaténation non ambigu. Semigroup Forum 18, 331–340 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pin, JÉ. (2013). An Explicit Formula for the Intersection of Two Polynomials of Regular Languages. In: Béal, MP., Carton, O. (eds) Developments in Language Theory. DLT 2013. Lecture Notes in Computer Science, vol 7907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38771-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-38771-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38770-8
Online ISBN: 978-3-642-38771-5
eBook Packages: Computer ScienceComputer Science (R0)