A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Undecidability of state complexity




TekijätArto Salomaa, Kai Salomaa, Sheng Yu

KustantajaTAYLOR & FRANCIS LTD

Julkaisuvuosi2013

JournalInternational Journal of Computer Mathematics

Tietokannassa oleva lehden nimiINTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Lehden akronyymiINT J COMPUT MATH

Numero sarjassa6

Vuosikerta90

Numero6

Aloitussivu1310

Lopetussivu1320

Sivujen määrä11

ISSN0020-7160

DOIhttps://doi.org/10.1080/00207160.2012.704994


Tiivistelmä

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.




Last updated on 2024-26-11 at 13:26