A deterministic incomplete automaton A = < Q, Sigma, delta > is partially monotonic if its state set Q admits a linear order such that each partial transformation delta(_, a) with a is an element of delta preserves the restriction of the order to the domain of the transformation. We show that if A possesses a 'killer' word w is an element of Sigma(*) whose action is nowhere defined, then A is 'killed' by a word of length vertical bar Q vertical bar + [(vertical bar Q vertical bar - 1)/(2)].
Язык оригиналаАнглийский
Название основной публикации9th International Conference on Developments in Language Theory, DLT 2005, Proceedings
Подзаголовок основной публикацииbook
ИздательSpringer Verlag
Страницы112-121
Число страниц10
Том3572
ISBN (печатное издание)3-540-26546-5
СостояниеОпубликовано - 2005

Серия публикаций

НазваниеLECTURE NOTES IN COMPUTER SCIENCE
ИздательSpringer Verlag
Том3572
ISSN (печатное издание)0302-9743

    Предметные области WoS

  • Компьютерные науки, Разработка программного обеспечения
  • Компьютерные науки, Теория и методы

    Предметные области ASJC Scopus

  • Computer Science (miscellaneous)
  • Theoretical Computer Science

ID: 41355429