A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Undecidability of state complexity
Tekijät: Arto Salomaa, Kai Salomaa, Sheng Yu
Kustantaja: TAYLOR & FRANCIS LTD
Julkaisuvuosi: 2013
Journal: International Journal of Computer Mathematics
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Lehden akronyymi: INT J COMPUT MATH
Numero sarjassa: 6
Vuosikerta: 90
Numero: 6
Aloitussivu: 1310
Lopetussivu: 1320
Sivujen määrä: 11
ISSN: 0020-7160
DOI: https://doi.org/10.1080/00207160.2012.704994
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.