Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v3(3-4)/nosov-269-279.pdf Дата изменения: Fri May 8 19:27:46 2009 Дата индексирования: Mon Oct 1 23:35:24 2012 Кодировка: Windows-1251

Критерий регулярности булевского неавтономного автомата с разделенным входом
В.А. Носов
В работе получен критерий регулярности неавтономного автомата с двоичными алфавитами, не сводящийся к проверке регулярности частичных функций перехода. Проверка регулярности неавтономного автомата сведена к проверке регулярности единственного семейства булевых функций и проверке свойства, названного правильностью, другого семейства булевых функций, причем оба семейства естественно ассоциированы с функцией перехода автомата.

1 Введение
Пусть A = (I , S, ) произвольный конечный автомат без выхода, где I множество входов, S множество состояний, : I Ч S S функция переходов. Автомат A называется регулярным (перестановочным) если для любого a I функция (i, s)|i=a является биекцией множества S . Будем предполагать, что автомат A задан в булевской форме, т.е. I = Ek , S = En множества двоичных наборов длин k и n соответственно, задано семейством из n булевских функций от k + n переменных x1 , . . . , xk , y1 , . . . , yn , где (x1 , . . . , xk ) Ek , (y1 , . . . , yn ) En , = (f1 , . . . fn ), fi = fi (x1 , . . . , xk , y1 , . . . , yn ), i 1, n. Будем предполагать также, что входы автомата A разделены, т.е. для всех i 1, n выполнено условие

fi = fi (xi , y1 , , . . . , yn )

(1)

(при этом k = n). Другими словами, при разделенном входе каждая функция fi зависит точно от одного бита входа. Регулярность автономных булевских автоматов рассматривалась в работах [1], [2], [3], в которых


был получен ряд критериев регулярности. Ясно, что вопрос о регулярности неавтономного автомата сводится к проверке регулярности |I | автономных автоматов, причем для булевской формы автомата |I | = 2k , а для случая разделенного входа |I | = 2n . Наша цель получить прямой критерий регулярности неавтономного булевского автомата с разделенным входом.

2 Переход к каноническим координатам
Пусть функция переходов автомата задана функциями (f1 , ..., fn ), где fi = fi (xi , y1 , . . . , yn ), i 1, n. Разложим каждую функцию fi по переменной xi в виде fi = gi ћ xi + hi , где gi = gi (y1 , . . . , yn ), hi = hi (y1 , . . . , yn ), i 1, n. Для регулярности автомата необходимо, чтобы функция (h1 , . . . , hn ) обладала свойством регулярности, поэтому, предполагая это условие выполненным, произведем замену переменных

hi (y1 , . . . , yn ) = zi ,

i = 1, n

Тогда функция переходов автомата представляется в виде

Fi (z1 , . . . , zn ) ћ xi + zi ,
где

i = 1, n

(2)

Fi = gi h-1 (z1 , . . . , zn ), . . . , h-1 (z1 , . . . , zn ) . 1 n

Про формулы (2) будем говорить, что функция переходов задана в канонических координатах. Для произвольного семейства булевских функций F1 , . . . , Fn от переменных z1 , . . . , zn определим -свойство (свойство правильности) условиями: Для любых (z1 , . . . , zn ) = (z1 , . . . , zn ) существует 1, n, такое, что z = z , F (z1 , . . . , zn ) = F (z1 , . . . , zn )

(3)

(x1 , . . . , xn ) необходимо и достаточно, чтобы для семейства функций (F1 , . . . , Fn ) выполнялось свойство правильности (3).

Лемма 1 Для регулярности семейства функций (2) при всех

Доказательство. Пусть семейство (F1 , . . . , Fn ) удовлетворяет условию

правильности (3). Пусть a = (a1 , . . . , an ), z = (z1 , . . . , zn ), z = (z1 , . . . , zn ) произвольные двоичные наборы, причем z = z . По 270


условию существует 1, n, такое, что выполнено z = z , F (z ) = F (z ). Тогда имеем z + a ћ F (z ) = z + a ћ F (z ) и, следовательно, семейство (2) регулярно при (x1 , . . . , xn )(a1 , . . . , an ). Пусть теперь семейство (F1 , . . . , Fn ) не удовлетворяет условию правильности (3). Значит, существуют наборы z и z , z = z , такие, что для всех 1, n, для которых z = z выполнено F (z ) = F (z ). Определим семейство a = (a1 , . . . , an ) где a = z + z , a 1, n. Для выбранных a имеем для всех 1, n

z + a F (z ) = z + a F (z ).
Это означает, что семейство функций (2) не регулярно при (x1 , . . . , xn ) = (a1 , . . . , an ).

3 Критерий правильности булевых функций

семейства

В предыдущем разделе приведен критерий проверки правильности семейств булевых функций, основанный на проверке табличных свойств функций. Рассмотрим задачу отыскания соответствующего критерия, основанного на проверке аналитических свойств функций, что может привести к построению более эффективных алгоритмов. В настоящем разделе дается такой критерий и показывается, что рассматриваемая задача является N P -трудной. Для семейства булевых функций f = (fi ), i = 1, n определим семейство f = (fi ), i = 1, n, где для любого i [1, n] имеем

fi = xi + fi
Пусть I некоторое множество индексов, где I [1, n] и I = ( ), I , < 0, 1 > семейство констант с индексами из множества I . Определим семейство функций аналогично предыдущему

0 fC I = (fi0 ), 0 f (x) = f (x)|

i CI

где C I дополнение множества I в [1, n], полагая для любого C I
x =

,

I

(1)

Другими словами, f 0 - это функции семейства f с индексами из множества C I , в которых переменные с индексами из I замещены константами семейства I . Справедлива
271


Лемма 2 Семейство

булевых функций f правильно тогда и только тогда, когда для любого множества I [1, n] и любого 0 семейства констант I семейство fC I будет регулярным, т.е. будет осуществлять взаимно однозначное отображение соответствующих наборов (xi ), i C I .

Доказательство аналогично доказательству леммы 1. Для дальнейшего нам понадобится один из критериев регулярности семейства булевых функций критерий Хаффмена [6]: семейство булевых функций f = (fi ), i = 1, n регулярно тогда и только тогда, когда все произведения fi1 , . . . , fis , 1 s n - 1 не содержат в приведенной полиномиальной записи члена x1 . . . xn , а произведение f1 . . . fn содержит такой член. Введем некоторые определения. Пусть f (x1 , . . . , xn ) булева функция от n переменных и I [1, n]. Множество переменных xI = (xi ), i I , где для определенности возьмем I = [1, s], 1 s n, будем называть существенным для функции f , если

f (1 , . . . , s , x
1 ,...,s

s+1

, . . . , xn ) 0 (сумма по модулю 2)

(2)

При s = 1 мы имеем определение существенности одного переменного. При s = n утверждение о существенности множества переменных (xi ), i [1, n] равносильно нечетности веса f . Легко проверить, что множество переменных xI = (xi ), i I существенно для функции f (x1 , . . . , xn ) тогда и только тогда, когда в канонической полиномиальной записи разложения функции f по переменным xi , i I коэффициент у произведения xi не будет тождественно равен нулю. Это следует из хорошо известного тождества
iI

f (x1 , ..., xn ) = =
1 ,...,
s

1 ,...,

f (1 , ..., s , x
s

s+1

, ..., xn )x1 ...xs = 1 s (3)

f (1 , ..., s , x

s+1

, ..., xn )(x1 + 1 + 1)...(xs + s + 1)

Для дальнейшего нам понадобятся две технические леммы, легко доказываемые непосредственно на основе определения.

Лемма 3 Если множество переменных xS = (xi ), i S , S [1, n]
существенно для функции f (x1 , . . . , xn ), то множество переменных xP = (xi ), i P , P [1, n] также будет существенным при P S .

функция f 0 (x1 , . . . , xn ) получена из функции f (y1 , . . . , ym ) путем замещения некоторых переменных константами.
272

Лемма 4 Пусть


Пусть множество переменных xI = (xi ), i I , I [1, n] существенно для функции f 0 (x1 , . . . , xn ). Тогда оно существенно и для функции f (y1 , . . . , ym ).
Справедлива следующая

Теорема 1 Семейство булевых функций f = (fi ), i [1, n] будет
правильным тогда и только тогда, когда для любого подмножества I , I [1, n] произведение функций fi не зависит существенно от множества переменных xI = (xi ), i I .
iI

Доказательство. Необходимость. Пусть условие для любого
подмножества I , I [1, n] произведение функций
iI

fi не зависит

существенно от множества переменных xI = (xi ), i I не выполняется. Значит существует I [1, n], для которого fi зависит существенно от xI = (xi ), i I . Из всех таких множеств выберем минимальное по включению множество. Пусть для определенности I = {i1 , . . . , is }. Покажем, что найдется набор констант, заместив которыми переменные xi , i C I , в функциях семейства fi = xi + fi , i I , получим нерегулярное 0 = (f 0 ), i I . семейство f i Рассмотрим произведение
iI

fi =
iI iI

(xi + fi ) =
iI

xi +
(L1 ,L2 ) iL
1

xi ћ
j L
2

fj +
iI

f

i

(4)

где сумма в (4) распространяется по всем разбиениям множества I на сумму непустых множеств L1 , L2 , т.е. таким L1 , L2 , что I = L1 L2 , L1 L2 = . fi существенно зависит от множества По условию, произведение переменных xI = (xi ), i I . Значит, существует набор констант C I для переменных с индексами из C I , такой, что функция
iI

fi |
iI

x =

,

CI

(5)

содержит член

Подставим данный соотношения (4). Покажем, что xi ћ
iL
1

iI

xi в приведенной канонической записи.
набор
j L

констант

C

I

в

остальные

члены

fj0 , где fj0 функция, получившаяся из fj при
2

подстановке констант, не содержит члена

при любых непустых L1 , L2 . Предположим противное. 273

iI

xi в канонической записи


Пусть произведение

xi ћ
iL1 j L
2

fj дает член

iI

xi в приведенной
j L2
2

канонической записи при некоторых L1 , L2 . Это значит, что имеет нечетное число членов, которые имеют вхождение члена противном случае при умножении на Тогда функция
j L2 iL

fj0

xi все члены
1

iI

xi уничтожатся.

iL

xi , в

fj0 может быть записана в виде xi (Q1 ((x ), L2 ) + Q2 ((x ), [1, n])) / (6)

fj0 =
j L2 iL
2

где полином Q1 ((x ), L2 ) не зависит от переменных с индексами из / L2 и имеет нечетное число членов, полином Q2 имеет степень меньшую, чем |L2 | по переменным xi , i L2 . Из (6) следует, что при x = 1, L2 коэффициент при / xi обращается в единицу и, значит, множество переменных xL2 = (xi ), i L2 будет существенным для функции fj0 , а значит по лемме 3 оно будет существенным и для функции
j L
2

iL

2

собственное подмножество, то это противоречит предположению о минимальности множества I . Значит, в соотношении (4) после замещения переменных x , C I указанными константами C I , получим только xi , которые уничтожаются, и функция fi0 два вхождения члена не будет содержать члена
iI

j L

fj . Поскольку L2 I

2

i I не удовлетворяет критерию Хаффмена для регулярности и согласно сделанному выше замечанию (лемма 2) семейство f не является правильным. Необходимость доказана. Достаточность. Пусть для любого подмножества I [1, n] произведение функций fi не зависит существенно от множества
переменных xI = (xi ), i I . Покажем, что отсюда следует правильность семейства f = (fi ), i [1, n]. Для этого достаточно показать, в силу 0 сделанного выше замечания, что семейство fC I = (fi0 ), i C I , fi0 = (xi + fi0 ), i C I удовлетворяет критерию регулярности Хаффмена при любом I [1, n] и любом семействе констант I . n n Пусть сначала I = . Рассмотрим произведение fi = (xi + fi ) и покажем, что оно содержит член
n i=1 i=1 i=1 iI

iI

xi . Следовательно, семейство f

0 I

= (fi0 ),

iI

xi .

274


Имеем
n n n

( xi + f i ) =
i=1 i=1

xi +
(L1 ,L2 ) iL
1

xi ћ
j L
2

fj +
i=1

fi ,

(7)

где сумма в (7) распространяется по всем непустым разбиениям (L1 , L2 ) множества [1, n]. Произведение
n

что при любых непустых L1 , L2 произведение
n i=1

i=1

fi не содержит члена

n

i=1

xi по условию. Покажем, xi ћ
1

iL

j L

fj не дает члена
2

xi .

Предположим противное и пусть существуют такие непустые L1 , L2 . Это значит, что fj содержит нечетное число членов, содержащих
j L
2

вхождение произведения

j L2

xj . Запишем

j L

fj в виде
2

L2 =
j L
2

fj =
j L2

xi ћ (Q1 ((x ), L2 )) + Q2 ((x ), [1, n]), /

(8)

где многочлен Q1 ((x ), L2 ) имеет нечетное число членов, а многочлен / Q2 имеет степень по переменным x , L2 меньшую, чем |L2 |. Полагая в (8) x = 1, L1 , получим Q1 ((x ) L2 ) = 1 и, значит, 0 2 при данной / L фиксации переменных x , L1 , существенно зависит от множества переменных xL2 = (xi ), i L2 . Значит, по лемме 3 и функция L2 также существенно зависит от xL2 = (xi ), i L2 , что противоречит условию. Значит, в (7) первый член
n i=1 n n i=1 i=1

xi не может уничтожиться и произведение

fi содержит член

xi .

Пусть теперь M [1, n] собственное подмножество. fi (xi + fi ) и покажем, что оно Рассмотрим произведение M =
n i=1 iM iM

не содержит члена Имеем
iM

xi при любом M [1, n].

(xi + fi ) =
iM

xi +
(L1 ,L2 ) iL1

xi ћ
j L
2

fj +
j M

fj ,

(9)

где сумма в (9) распространяется по всем непустым разбиениям (L1 , L2 ) множества M . 275


Произведение

бы, что множество переменных (xi ), i [1, n] существенно для M = fi , а значит и его подмножество xM = (xi ), i M по лемме 3 также
iM

iM

fi не содержит члена

n i=1

xi , поскольку это означало

существенно для M , что противоречит условию. Далее, для любых непустых L1 , L2 произведение
n i=1

xi ћ
iL
1

f
j L
2

j

не может давать члена

xi . Если, напротив, это имеет место для
j L

фиксированных L1 , L2 , то имеющих вхождение
iC L1

fj содержит нечетное число членов,
2

xi , где C L1 дополнение множества L1 в [1, n].

Аналогично проделанному выше, представляем

L2 =
j L
2

fj =
iC L1

xi ћ (Q1 ((x ), L1 )) + Q2 ((x ), [1, n]),

(10)

где Q1 имеет нечетное число членов, Q2 имеет степень по переменным x , C L1 меньшую, чем |C L1 |. Полагая в (10) x = 1, L1 , получаем Q1 = 1 и, значит, 0 2 L существенно зависит от (xi ), i C L1 . Следовательно, и L2 существенно зависит от (xi ), i C L1 . Поскольку L2 C L1 , то L2 существенно зависит и от xL2 = (xi ), i L2 , что противоречит условию. Таким образом, в (9) нет членов, дающих произведение
n n i=1 i=1

xi .
n i=1

Таким образом, семейство f таково, что
iM

fi содержит член

xi , а

fi не содержит члена

n i=1

xi при любом M [1, n]. Значит, согласно

критерию Хаффмена, семейство f будет регулярным, и случай I = разобран полностью. Пусть теперь I = , C I = и I соответствующее произвольное 0 множество констант. Покажем, что соответствующее семейство fC I будет регулярным. Снова проверим выполнение критерия Хаффмена. Рассмотрим 0 I = (xi + fi0 ). C Имеем
iC I

0 I = C
iC I

xi +
(L1 ,L2 ) iL
1

xi ћ
j L
2

fj0 +
iC I

fi0 ,

(11)

где сумма распространяется по всем непустым разбиениям L1 , L2 множества C I . 276


Аналогично предыдущему,

f
iC I

0 i

не содержит члена

как в противном случае множество переменных (xi ), i C I было бы существенным для 0 I , а следовательно, существенным и для C I , что C противоречило бы условию. Далее, произведение xi ћ fj0 также не содержит члена xi при любых непустых L1 , L2 . Если это не так, например для фиксированного fj0 содержит нечетное число разбиения L1 , L2 , то в этом случае
j L iL
1

iC I

xi , так

j L

2

iC I

членов, содержащих вхождение

iL

xi . Представляя
2

2

j L

fj0 в виде
2

xi ћ Q1 ((x ), L1 ) + Q2 ((x ), C I ),
iL
2

(12)

где Q1 имеет нечетное число членов, Q2 имеет степень по переменным x , L2 меньшую, чем |L2 | и, полагая в (12) x = 1, L1 , убеждаемся, что fj0 существенно зависит от (xi ), i L2 . Значит и fj существенно зависит от данного множества переменных. Последнее противоречит условию. Значит, в (11) член xi не может уничтожиться. Аналогично показывается, что функция M =
iC I iM j L2 j L
2

(xi + fi0 ), где M xi . Имеем (13)

C I собственное подмножество, не содержит члена M =
iM

iC I

xi +
(L1 ,L2 ) iL
1

xi ћ
j L
2

fj0 +
iM

f

0 i

(сумма по всем непустым разбиениям (L1 , L2 ) множества M ). Если произведение fi0 дает член xi , то аналогично предыдущему, множество переменных xM = (xi ), i M будет существенным для fi , что противоречит условию. Произведение
iM iM iC I

xi ћ
iL1 j L
2

fj0 также не дает члена
j L2

iC I

xi при любых

непустых L1 , L2 . В противном случае 0 2 = L членов, содержащих вхождение
iC L
1

fj0 имеет нечетное число

xi , C L1 дополнение L1 в C I .

Полагая x = 1, C I , C L1 , в 0 2 получаем, что / L 00 соответствующая функция L2 существенно зависит от множества переменных xC L1 = (xi ), i C L1 . Следовательно, эти переменные 277


существенны и для L2 , а значит L2 существенно зависит от xL2 = (xi ), i L2 , поскольку L2 C L1 . Согласно (13), функция M не 0 содержит члена xi . По критерию Хаффмена семейство fC I будет регулярным, а значит, согласно отмеченному выше, исходное семейство будет правильным. Теорема доказана. Покажем теперь, что если P = N P , то для задачи проверки правильности произвольного семейства функций не существует полиномиальных разрешающих алгоритмов. Аналогичное явление имеет место и для задачи проверки регулярности [5]. Справедлива
iC I

1, n от переменных x1 , . . . , xn , заданных в КНФ. Тогда задача проверки правильности семейства f является N P -трудной.

Теорема 2 Пусть дано семейство n булевых функций f = (fi ), i =

Доказательство. Пусть f (x1 , . . . , xn ) произвольная индивидуальная

задача "выполнимость". Рассмотрим следующее семейство из n + 1 булевых функций f = (1, . . . , 1, xn+1 ћ f (x1 , . . . , xn )), где xn+1 новая переменная. Ясно, что семейство f строится по функции f за полиномиальное время. Нетрудно проверить, что семейство f будет правильным тогда и только тогда, когда функция f не выполнима. Значит, если имеется полиномиальный алгоритм проверки правильности произвольного семейства, то, применяя его к семейству f , получаем полиномиальный алгоритм проверки выполнимости произвольной КНФ, которая является N P -полной задачей [5]. Таким образом, установлено, что задача проверки регулярности неавтономного булевского автомата с разделенным входом сводится к проверке регулярности семейства булевых функций, получаемых на нулевом входе, и проверке правильности семейства булевых функций, получаемого при переходе к каноническим координатам.
n

Список литературы
[1] Клосс Б.М., Малышев В.А. Определение регулярности автомата по его каноническим уравнениям. ДАН СССР, 1967, т. 172, N 3, с. 543546. [2] Клосс Б.М., Нечипорук Э.И. О классификации функций многозначной логики. Пробл. кибернетики, 1963, вып. 3, с. 2736. 278


[3] Применко Э.А., Скворцов Э.Ф. Об условиях регулярности конечных автономных автоматов. Дискретная математика, 1990, т. 2, вып. 1, с. 26-30. [4] Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш. Введение в теорию абстрактных автоматов. МГУ, 1985. [5] Алексеев В.Б., Носов В.А. N P -полные задачи и их полиномиальные варианты. Обзор. Обозрение прикладной и промышленной математики, 1997, т. 4, вып. 2, с. 165-193. [6] Human D.A. Canonical forms for information lossless nite-state logical machines. IRE Trans. Circ. Theory, 1959, v. 6, p. 41-59.

279