Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Undecidability of State Comple...

Undecidability of State Complexity

Arto Salomaa, Kai Salomaa, Sheng Yu, Undecidability of State Complexity. International Journal of Computer Mathematics 90(6), 1310–1320, 2013.

Abstract:

The specific operations of intersection and
marked concatenation are considered. An infinite sequence C(i), i=1,2,..., of compositions of these two operations is constructed, as well as an infinite sequence of polynomials P(i),i=1,2,..., with positive integer coefficients. It is undecidable whether
or not P(i) is a state complexity function of
C(i). All languages are over a fixed finite alphabet. Also generalizations and open problems are presented.

BibTeX entry:

@ARTICLE{jSaSaYu13a,
  title = {Undecidability of State Complexity},
  author = {Salomaa, Arto and Salomaa, Kai and Yu, Sheng},
  journal = {International Journal of Computer Mathematics},
  volume = {90},
  number = {6},
  pages = {1310–1320},
  year = {2013},
  keywords = {finite automaton, state complexity, composition of operations},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication