Decision trees for regular language word recognition

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this paper the problem of recognition of words with fixed length from a regular language is considered. The word under consideration can be interpreted as a description of certain screen image in the following way: the i-th letter of the word encodes the color of the i-th screen cell. In this case a decision tree which recognizes some words may be interpreted as an algorithm for the recognition of images which are defined by considered words. The classification of all regular languages depending on the growth of minimal depth of decision trees for language word recognition with the growth of the word length is obtained. In proofs methods of test theory and rough set theory are used.
Original languageEnglish (US)
Pages (from-to)449-461
Number of pages13
JournalFundamenta Informaticae
Issue number4
StatePublished - Jan 1 2000
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-21

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Algebra and Number Theory
  • Theoretical Computer Science
  • Information Systems


Dive into the research topics of 'Decision trees for regular language word recognition'. Together they form a unique fingerprint.

Cite this