![Sample our Bioscience journals, sign in here to start your access, Latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5925/TOC-Subject-Sample-2021-Bioscience.jpg"})
Abstract
We consider the state complexity of compositions of regularity-preserving language operations. As our main result, we establish that determining the state complexity of an operation composed just from intersections and marked concatenations is undecidable. The proof relies on the undecidability of Hilbert's Tenth Problem. The languages used in the construction are over a fixed alphabet with at most 50 letters. We also consider some implications and generalizations, as well as discuss open problems.
2010 AMS Subject Classification::
Acknowledgements
This work was supported by Natural Science and Engineering Council of Canada Discovery Grants 147224 and 41630. A preliminary version of this paper was presented at LATA 2011.