Decision trees for regular factorial languages
In this paper, we study arbitrary regular factorial languages over a finite alphabet Σ. For the set of words L(n)of the length n belonging to a regular factorial language L, we investigate the depth of decision trees solving the recognition and the membership problems deterministically and nondeterm...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2022-09-01
|
| Series: | Array |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2590005622000510 |
| _version_ | 1828419922216091648 |
|---|---|
| author | Mikhail Moshkov |
| author_facet | Mikhail Moshkov |
| author_sort | Mikhail Moshkov |
| collection | DOAJ |
| description | In this paper, we study arbitrary regular factorial languages over a finite alphabet Σ. For the set of words L(n)of the length n belonging to a regular factorial language L, we investigate the depth of decision trees solving the recognition and the membership problems deterministically and nondeterministically. In the case of recognition problem, for a given word from L(n), we should recognize it using queries each of which, for some i∈{1,…,n}, returns the ith letter of the word. In the case of membership problem, for a given word over the alphabet Σ of the length n, we should recognize if it belongs to the set L(n)using the same queries. For a given problem and type of trees, instead of the minimum depth h(n)of a decision tree of the considered type solving the problem for L(n), we study the smoothed minimum depth H(n)=max{h(m):m≤n}. With the growth of n, the smoothed minimum depth of 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 cases (decision trees solving the problem of recognition nondeterministically, and decision trees solving the membership problem deterministically and nondeterministically), with the growth of n, the smoothed minimum depth of decision trees is either bounded from above by a constant or grows linearly. As corollaries of the obtained results, we study joint behavior of smoothed minimum depths of decision trees for the considered four cases and describe five complexity classes of regular factorial languages. We also investigate the class of regular factorial languages over the alphabet {0,1}each of which is given by one forbidden word. |
| first_indexed | 2024-12-10T15:02:38Z |
| format | Article |
| id | doaj.art-01e0dd653cac4e59b464c74b3fe5bff5 |
| institution | Directory Open Access Journal |
| issn | 2590-0056 |
| language | English |
| last_indexed | 2024-12-10T15:02:38Z |
| publishDate | 2022-09-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Array |
| spelling | doaj.art-01e0dd653cac4e59b464c74b3fe5bff52022-12-22T01:44:07ZengElsevierArray2590-00562022-09-0115100203Decision trees for regular factorial languagesMikhail Moshkov0Computer, Electrical and Mathematical Sciences and Engineering Division and Computational Bioscience Research Center, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi ArabiaIn this paper, we study arbitrary regular factorial languages over a finite alphabet Σ. For the set of words L(n)of the length n belonging to a regular factorial language L, we investigate the depth of decision trees solving the recognition and the membership problems deterministically and nondeterministically. In the case of recognition problem, for a given word from L(n), we should recognize it using queries each of which, for some i∈{1,…,n}, returns the ith letter of the word. In the case of membership problem, for a given word over the alphabet Σ of the length n, we should recognize if it belongs to the set L(n)using the same queries. For a given problem and type of trees, instead of the minimum depth h(n)of a decision tree of the considered type solving the problem for L(n), we study the smoothed minimum depth H(n)=max{h(m):m≤n}. With the growth of n, the smoothed minimum depth of 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 cases (decision trees solving the problem of recognition nondeterministically, and decision trees solving the membership problem deterministically and nondeterministically), with the growth of n, the smoothed minimum depth of decision trees is either bounded from above by a constant or grows linearly. As corollaries of the obtained results, we study joint behavior of smoothed minimum depths of decision trees for the considered four cases and describe five complexity classes of regular factorial languages. We also investigate the class of regular factorial languages over the alphabet {0,1}each of which is given by one forbidden word.http://www.sciencedirect.com/science/article/pii/S2590005622000510Regular factorial languageRecognition problemMembership problemDeterministic decision treeNondeterministic decision tree |
| spellingShingle | Mikhail Moshkov Decision trees for regular factorial languages Array Regular factorial language Recognition problem Membership problem Deterministic decision tree Nondeterministic decision tree |
| title | Decision trees for regular factorial languages |
| title_full | Decision trees for regular factorial languages |
| title_fullStr | Decision trees for regular factorial languages |
| title_full_unstemmed | Decision trees for regular factorial languages |
| title_short | Decision trees for regular factorial languages |
| title_sort | decision trees for regular factorial languages |
| topic | Regular factorial language Recognition problem Membership problem Deterministic decision tree Nondeterministic decision tree |
| url | http://www.sciencedirect.com/science/article/pii/S2590005622000510 |
| work_keys_str_mv | AT mikhailmoshkov decisiontreesforregularfactoriallanguages |