1
$\begingroup$

From what I know,

  • a problem can be transformed to a yes/no answer, which can be described by a decision tree.
  • Solution to a problem also can be represented by a set of strings (a language), which means the problem can be regarded as a membership problem.
  • This set of strings can also be represented by an automaton, although how it is done is still vague in my mind.

My questions are:

  1. What is the relationship between a decision tree and an automaton?

  2. How to convert a decision tree to an automaton?

I have tried to read some articles related to this, and somehow 'know' these concepts are related with each other, but still feel that I don't quite understand the relation and how to convert them to each other.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context) is a model of computation which describes a language.

The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision tree to an automaton.

Here are some examples:

  • Determining whether a person is overweight given their age, gender, height, and weight. This can be solved by a decision tree, or by a table.
  • Deciding whether a 64x64 image describes a dog or a cat. This can also be solved by a decision tree, though that's not recommended.
  • Deciding whether a given integer is a prime. This decision problem defines a language, the language of primes. Agrawal, Kayal and Saxena gave an efficient procedure for solving this problem in 2002, which however cannot be implemented by the kind of automata usually considered in theory of computation classes (DFA, NFA, PDA).
  • Deciding whether a given string is a palindrome. This decision problem defines a language, and can be solved by a pushdown automaton, but not by a DFA/NFA.
Improve this answer
$\endgroup$
7
  • $\begingroup$ Yuval, thank you for your prompt reply and precious insights. Seems like there's not much reason to convert a decision tree to an automaton, but do you have any hint on how to convert anyway..? $\endgroup$
    – kate
    Sep 21, 2020 at 9:16
  • 1
    $\begingroup$ A decision tree corresponds to a language of strings of length $n$. In particular, the language is finite. It is easy to construct a DFA for a finite language. $\endgroup$
    – Yuval Filmus
    Sep 21, 2020 at 10:00
  • $\begingroup$ I see. So it means: decision tree --> language --> automaton. Thank you so much :D $\endgroup$
    – kate
    Sep 21, 2020 at 13:16
  • 1
    $\begingroup$ The language of a decision tree consists of all words in the domain which lead the tree to Yes. If you take all paths, the language wouldn’t depend on the tree at all. $\endgroup$
    – Yuval Filmus
    Sep 23, 2020 at 6:23
  • 1
    $\begingroup$ No, we don't need to define it. It is part of the standard semantics of decision trees. $\endgroup$
    – Yuval Filmus
    Sep 23, 2020 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.