Algorithmic Problems. Local Approach

Mikhail Moshkov

doi:10.1007/978-3-030-41728-4_16

Algorithmic Problems. Local Approach

Mikhail Moshkov^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

In this chapter, we study algorithmic problems related to the local approach to the investigation of decision trees: problems of computation of the minimum complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees, problems of construction of decision trees with the minimum complexity, and the problem of solvability of systems of equations over information systems. We study relationships among these problems and describe all variants of algorithmic problem behavior. We also discuss an algorithm for decision table construction and two algorithms that construct deterministic decision trees.

Original language	English (US)
Title of host publication	Intelligent Systems Reference Library
Publisher	Springer
Pages	195-202
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-030-41728-4_16
State	Published - 2020

Publication series

Name	Intelligent Systems Reference Library
Volume	179
ISSN (Print)	1868-4394
ISSN (Electronic)	1868-4408

Bibliographical note

Publisher Copyright:
© 2020, The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG.

ASJC Scopus subject areas

General Computer Science
Information Systems and Management
Library and Information Sciences

Access to Document

10.1007/978-3-030-41728-4_16

Cite this

@inbook{8a263d51356d40f9b33b9bd28e6d88ae,

title = "Algorithmic Problems. Local Approach",

abstract = "In this chapter, we study algorithmic problems related to the local approach to the investigation of decision trees: problems of computation of the minimum complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees, problems of construction of decision trees with the minimum complexity, and the problem of solvability of systems of equations over information systems. We study relationships among these problems and describe all variants of algorithmic problem behavior. We also discuss an algorithm for decision table construction and two algorithms that construct deterministic decision trees.",

author = "Mikhail Moshkov",

note = "Publisher Copyright: {\textcopyright} 2020, The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2020",

doi = "10.1007/978-3-030-41728-4_16",

language = "English (US)",

series = "Intelligent Systems Reference Library",

publisher = "Springer",

pages = "195--202",

booktitle = "Intelligent Systems Reference Library",

address = "Germany",

}

TY - CHAP

T1 - Algorithmic Problems. Local Approach

AU - Moshkov, Mikhail

PY - 2020

Y1 - 2020

N2 - In this chapter, we study algorithmic problems related to the local approach to the investigation of decision trees: problems of computation of the minimum complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees, problems of construction of decision trees with the minimum complexity, and the problem of solvability of systems of equations over information systems. We study relationships among these problems and describe all variants of algorithmic problem behavior. We also discuss an algorithm for decision table construction and two algorithms that construct deterministic decision trees.

AB - In this chapter, we study algorithmic problems related to the local approach to the investigation of decision trees: problems of computation of the minimum complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees, problems of construction of decision trees with the minimum complexity, and the problem of solvability of systems of equations over information systems. We study relationships among these problems and describe all variants of algorithmic problem behavior. We also discuss an algorithm for decision table construction and two algorithms that construct deterministic decision trees.

UR - http://www.scopus.com/inward/record.url?scp=85083451706&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-41728-4_16

DO - 10.1007/978-3-030-41728-4_16

M3 - Chapter

AN - SCOPUS:85083451706

T3 - Intelligent Systems Reference Library

SP - 195

EP - 202

BT - Intelligent Systems Reference Library

PB - Springer

ER -

Algorithmic Problems. Local Approach

Abstract

Publication series

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this