Օբյեկտ

Վերնագիր: The splitting technique in monotone recognition

Հեղինակ:

Aslanyan Levon

Տեսակ:

Article

Համահեղինակ(ներ):

Sahakyan Hasmik

Ամփոփում:

We consider the problem of query based algorithmic identification/recognition of monotone Boolean functions, as well as of binary functions defined on multi-valued discrete grids. Hansel's chain-split technique of n -cubes is a well known effective tool of monotone Boolean recognition. An extension by Alekseev is already applied to the grid case. The practical monotone recognition on n -cubes is provided by the so called chain-computation algorithms that is not extended to the case of multi-valued grids. We propose a novel split construction based on partitioning the grid into sub-grids and into discrete structures that are isomorphic to binary cubes. Monotonicity in a multi-valued grid implies monotonicity in all induced binary cubes and in multi-valued sub-grids. Applying Hansel's technique for identification of monotone Boolean functions on all appearing binary cubes, and Alekseev's algorithm on all sub-grids leads to different scenarios of reconstruction of monotone functions. On one hand such partitioning technique makes parallel recognition possible, on the other hand - the method can be used in practical identification algorithms due to simple structures and easily calculable quantities appearing after the partition to the n -cubes. Complexity issues of considered algorithms were also elaborated.

Հրատարակության վայրը:

Elsevier Science Publishers B. V., Netherlands

Հրատարակիչ:

Elsevier

Հրատարակման ամսաթիվ:

10.01.2017

Նույնականացուցիչ:

oai:noad.sci.am:136088

DOI:

10.1016/j.dam.2016.04.008

ISSN:

0166-218X

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Discrete Applied Mathematics

Հատոր:

216

Համար:

P3

URL:


Կազմակերպության անվանում:

Institute for Informatics and Automation Problems

Երկիր:

Armenia

Ինդեքսավորում:

WOS

Օբյեկտի հավաքածուներ:

Վերջին անգամ ձևափոխված:

Apr 9, 2021

Մեր գրադարանում է սկսած:

Apr 9, 2021

Օբյեկտի բովանդակության հարվածների քանակ:

23

Օբյեկտի բոլոր հասանելի տարբերակները:

https://noad.sci.am/publication/149570

Ցույց տալ նկարագրությունը RDF ձևաչափով:

RDF

Ցույց տալ նկարագրությունը OAI-PMH ձևաչափով։

OAI-PMH

Հրատարակության անուն Ամսաթիվ
Levon Aslanyan, The splitting technique in monotone recognition Apr 9, 2021

Օբյեկտներ

Նման

Այս էջը օգտագործում է 'cookie-ներ'։ Ավելի տեղեկատվություն