Find in Library

In this paper, we study arbitrary subword-closed languages over the alphabet <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>}</mo></mrow></semantics></math></inline-formula> (binary subword-closed languages). For the set of words <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>L</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> of the length <i>n</i> belonging to a binary subword-closed language <i>L</i>, we investigate the depth of the decision trees solving the recognition and the membership problems deterministically and nondeterministically. In the case of the recognition problem, for a given word from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>L</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula>, we should recognize it using queries, each of which, for some <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>∈</mo><mo>{</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>n</mi><mo>}</mo></mrow></semantics></math></inline-formula>, returns the <i>i</i>th letter of the word. In the case of the membership problem, for a given word over the alphabet <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>}</mo></mrow></semantics></math></inline-formula> of the length <i>n</i>, we should recognize if it belongs to the set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>L</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></semantics></math></inline-formula> using the same queries. With the growth of <i>n</i>, the minimum depth of the decision trees solving the problem of recognition deterministically is either bounded from above by a constant or grows as a logarithm, or linearly. For other types of trees and problems (decision trees solving the problem of recognition nondeterministically and decision trees solving the membership problem deterministically and nondeterministically), with the growth of <i>n</i>, the minimum depth of the decision trees is either bounded from above by a constant or grows linearly. We study the joint behavior of the minimum depths of the considered four types of decision trees and describe five complexity classes of binary subword-closed languages.