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)].
Original languageEnglish
Title of host publication9th International Conference on Developments in Language Theory, DLT 2005, Proceedings
Subtitle of host publicationbook
PublisherSpringer Verlag
Pages112-121
Number of pages10
Volume3572
ISBN (Print)3-540-26546-5
Publication statusPublished - 2005

Publication series

NameLECTURE NOTES IN COMPUTER SCIENCE
PublisherSpringer Verlag
Volume3572
ISSN (Print)0302-9743

    WoS ResearchAreas Categories

  • Computer Science, Software Engineering
  • Computer Science, Theory & Methods

    ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Theoretical Computer Science

ID: 41355429