How to convert a decision tree to an automaton?

Question

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.

Answer 1

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.