Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец
Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца. Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обобщенной задачи. Запропоновано узагальнення відомої задачі задовільнення обмеж...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2015 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/112574 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец / Е.В. Водолазский // Управляющие системы и машины. — 2015. — № 6. — С. 3–7, 42. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862720353889943552 |
|---|---|
| author | Водолазский, Е.В. |
| author_facet | Водолазский, Е.В. |
| citation_txt | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец / Е.В. Водолазский // Управляющие системы и машины. — 2015. — № 6. — С. 3–7, 42. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца. Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обобщенной задачи.
Запропоновано узагальнення відомої задачі задовільнення обмежень в термінах операцій комукативного напівкільця. Показано, що відомий поліноміально розв’язний підклас задач з мажоритарним поліморфізмом є розв’язним і для узагальненої задачі.
The article generalizes the known constraint satisfaction problems in terms of a commutative semiring. It is shown that a known track table subclass with a majority polymorphism is also track table in the generalized problem. The constraint satisfaction problems can be defined as computing the disjunction over the set of all variable values of all constraints conjunction. This definition can be generalized to computing the sum of products in a commutative semi ring. One of the track table subclasses of the classical constraint satisfaction problems semering are problems with a majority polymorphism. The article generalizes the definition of polymorphisms to commutative semi rings with the idempotent sum and product and defines a track table subclass for the generalized problem. Many of the useful properties of the classical polymorphisms proved to be true with the generalized polymorphism definition. It is shown that any generalized constraint satisfaction problem with a majority polymorphism can be solved in polynomial time. An algorithm that solves the problem is given and is based on the equivalent star to simplex transformations of the problem by excluding variables one at a time.
|
| first_indexed | 2025-12-07T18:25:01Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-112574 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-12-07T18:25:01Z |
| publishDate | 2015 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Водолазский, Е.В. 2017-01-23T16:18:18Z 2017-01-23T16:18:18Z 2015 Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец / Е.В. Водолазский // Управляющие системы и машины. — 2015. — № 6. — С. 3–7, 42. — Бібліогр.: 6 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/112574 519. 6 Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца. Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обобщенной задачи. Запропоновано узагальнення відомої задачі задовільнення обмежень в термінах операцій комукативного напівкільця. Показано, що відомий поліноміально розв’язний підклас задач з мажоритарним поліморфізмом є розв’язним і для узагальненої задачі. The article generalizes the known constraint satisfaction problems in terms of a commutative semiring. It is shown that a known track table subclass with a majority polymorphism is also track table in the generalized problem. The constraint satisfaction problems can be defined as computing the disjunction over the set of all variable values of all constraints conjunction. This definition can be generalized to computing the sum of products in a commutative semi ring. One of the track table subclasses of the classical constraint satisfaction problems semering are problems with a majority polymorphism. The article generalizes the definition of polymorphisms to commutative semi rings with the idempotent sum and product and defines a track table subclass for the generalized problem. Many of the useful properties of the classical polymorphisms proved to be true with the generalized polymorphism definition. It is shown that any generalized constraint satisfaction problem with a majority polymorphism can be solved in polynomial time. An algorithm that solves the problem is given and is based on the equivalent star to simplex transformations of the problem by excluding variables one at a time. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Теоретические проблемы обработки и распознавания Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец Узагальнені завдання розмітки з мажоритарних поліморфізмом для деякого класу півкілець Generalized Labelling Problems with a Majority Polymorphism for a Certain Class of Semirings Article published earlier |
| spellingShingle | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец Водолазский, Е.В. Теоретические проблемы обработки и распознавания |
| title | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_alt | Узагальнені завдання розмітки з мажоритарних поліморфізмом для деякого класу півкілець Generalized Labelling Problems with a Majority Polymorphism for a Certain Class of Semirings |
| title_full | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_fullStr | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_full_unstemmed | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_short | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_sort | обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| topic | Теоретические проблемы обработки и распознавания |
| topic_facet | Теоретические проблемы обработки и распознавания |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/112574 |
| work_keys_str_mv | AT vodolazskiiev obobŝennyezadačirazmetkismažoritarnympolimorfizmomdlânekotorogoklassapolukolec AT vodolazskiiev uzagalʹnenízavdannârozmítkizmažoritarnihpolímorfízmomdlâdeâkogoklasupívkílecʹ AT vodolazskiiev generalizedlabellingproblemswithamajoritypolymorphismforacertainclassofsemirings |