Представления автоматов в локально определенных классах
Saved in:
| Published in: | Труды Института прикладной математики и механики НАН Украины |
|---|---|
| Date: | 2008 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут прикладної математики і механіки НАН України
2008
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/20012 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Представления автоматов в локально определенных классах / В.А. Козловский, О.М. Копытова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 80-87. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859635425796161536 |
|---|---|
| author | Козловский, В.А. Копытова, О.М. |
| author_facet | Козловский, В.А. Копытова, О.М. |
| citation_txt | Представления автоматов в локально определенных классах / В.А. Козловский, О.М. Копытова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 80-87. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Труды Института прикладной математики и механики НАН Украины |
| first_indexed | 2025-12-07T13:15:20Z |
| format | Article |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2008. Том 17
УДК 519.7
c©2008. В.А. Козловский, О.М. Копытова
ПРЕДСТАВЛЕНИЯ АВТОМАТОВ В
ЛОКАЛЬНО ОПРЕДЕЛЕННЫХ КЛАССАХ
Найдены достаточные, а при дополнительных ограничениях и необходимые условия, при кото-
рых частичные автоматы являются представлениями автоматов относительно введенных локально
определенных классов автоматов, полученных из эталона некоторыми перебросками дуг. Для таких
представлений получены неулучшаемые для n-плотных классов автоматов оценки сложности пред-
ставлений автоматов. Для их частных случаев – кратчайших простых контрольных экспериментов,
показано, что длина последних отличается от длины кратчайших обходов ровно на единицу.
Введение. Контрольные эксперименты с автоматами [1] обычно изучаются для
достаточно обширных классов автоматов. На уровне абстрактного автомата боль-
шинство таких классов можно рассматривать как результат последовательности спе-
циальных преобразований множества дуг автомата-эталона типа переброски дуг –
замены конца одной из дуг графа переходов автомата другим состоянием, или за-
мены в отметке дуги одного выходного символа другим. В [2] рассматривались так
называемые m-плотные классы, охватывающие широкий круг классов автоматов,
возникающих при произвольных перебросках дуг или изменении их отметок, воз-
можно, даже с увеличением числа состояний. Для таких классов необходимым усло-
вием, при котором эксперимент становится контрольным, является обход по всем
дугам графа переходов автомата-эталона. Однако это условие обычно не является
достаточным, что является одной из причин высокой сложности задачи распозна-
вания свойства "быть контрольным экспериментом" относительно этих классов (в
ряде случаев это NP -полная проблема [3]). Исключением является класс локально
порожденных из эталона автоматов [4], для которого, при наложении ограничений
на поведение эталона, минимальный контрольный эксперимент "почти" совпадает
с обходом по всем дугам автомата-эталона. Это сразу же определяет и полиноми-
альность указанной задачи распознавания в этом случае. Поэтому интерес пред-
ставляет поиск достаточно разнообразных по своему составу классов, для которых
"почти" обходы определяют контрольные эксперименты. "Почти" обходы характе-
ризуются наименьшей сложностью среди контрольных экспериментов относительно
m-плотных классов, то есть, в них прообраз каждой дуги исходного автомата встре-
чается минимально возможное число раз. Стоит заметить,что, например, в род-
ственной задаче тестирования программных систем на основе графовых моделей
чаще всего ограничиваются построением обхода по дугам соответствующих графов,
хотя обход есть лишь необходимое условие для полноты проверки. В работе рас-
сматриваются обобщения контрольных экспериментов – представления минималь-
ной сложности для автоматов [3] относительно так называемых локально опреде-
ленных классов [5]. Показывается, что в этом случае необходимое условие обхода
80
Представления автоматов в локально определенных классах
при некоторых дополнительных предположениях является также и достаточным.
1. Автоматы и представления. Под автоматом будем понимать автомат Ми-
ли A = (S, X, Y, δ, λ), где S, X, Y – алфавиты состояний, входов и выходов соот-
ветственно, а δ, λ – функции переходов и выходов, в общем случае, частичные. В
дальнейшем, если не оговорено противное, рассматриваются автоматы, у которых
области определения функций переходов и выходов совпадают. Функции автомата
обычным образом распространяются на множество X∗. Будем говорить, что вход-
выходное слово w = (p, q) порождается состоянием s автомата A, если λ(s, p) = q.
С каждым состоянием s ассоциируется множество λs всех вход-выходных слов, по-
рождаемых этим состоянием. Автомат A удобно задавать в виде графа переходов,
вершинами которого являются состояния из S, а дугами – четверки (s, x, y, t) = u,
где δ(s, x) = t, λ(s, x) = y. Пара (x, y) называется отметкой дуги u, s – ее началом,
а t – концом. В дальнейшем будем отождествлять автомат A со множеством всех
дуг его графа и писать u ∈ A, если u есть дуга автомата A. Множество всех дуг
автомата будем обозначать также как UA. Если не оговорено противное, считаем,
что автомат имеет хотя бы одну дугу. Состояние t называется достижимым из s,
если t ∈ δ(s, p) для некоторого p ∈ X∗. Автомат называется сильно связным, если
его граф переходов сильно связен. Состояние s называется преходящим в A, если
s не является концом ни одной дуги автомата A, и висячим, если s не является
началом ни одной дуги. Автомат, граф переходов которого не имеет циклов, назо-
вем ацикличным. Если необходимо, алфавиты и функции автомата будем снабжать
индексами.
Множество W вход-выходных слов назовем экспериментом автомата A, если
W ⊆ λs для некоторого состояния s автомата A. Эксперимент W называется про-
стым, если он состоит из одного вход-выходного слова, и кратным в противном
случае. Обозначим ΦA множество экспериментов автомата A, l(w) – длину слова
w ∈ λs, λi
s – множество всех вход-выходных слов длины i, порождаемых состоянием
s. Эксперимент определяет множество путей в графе переходов автомата из состо-
яния s, и если оно содержит (покрывает) все множество дуг графа переходов, то
эксперимент называем обходом автомата из состояния s.
Пусть F – некоторый класс автоматов. Эксперимент W ∈ ΦA называется кон-
трольным для (A,F ), если из того, что W ∈ ΦB, B ∈ F , следует, что B содержит
подавтомат, эквивалентный A. Обычно класс F выбирается так, что вместо экви-
валентности рассматривается изоморфизм. Контрольные эксперименты являются
частным случаем представлений автоматов [3]. Приведем один из вариантов опре-
деления представлений.
Пусть A = (S, X, Y, δA, λA) и B = (T, X, Y, δB, λB) – некоторые автоматы. Гомо-
морфизмом автомата A в автомат B называется такое отображение множества S
во множество T , для которого, если дуга u = (s1, x, y, s2) принадлежит автомату
A, то дуга v = (ϕ(s1), x, y, ϕ(s2)) принадлежит B. Гомоморфизм ϕ индуцирует, та-
ким образом, отображение множества дуг автомата A во множество дуг автомата
B, которое будем обозначать тем же символом ϕ, и писать в этом случае ϕ(u) = v.
Гомоморфизм называем полным, если всякая дуга автомата B имеет прообраз в
81
В.А. Козловский, О.М. Копытова
автомате A. В этом случае B называем гомоморфным образом A по ϕ, что обозна-
чаем равенством B = ϕ(A). Полный изоморфизм обозначаем равенством A = B, а
наличие гомоморфизма A в B – неравенством A ≤ B.
Фрагментом автомата A называется всякий (частичный) автомат R, гомоморф-
но отображающийся в A [3]. Фрагмент автомата A назовем полным, если при любом
его гомоморфизме в этот автомат каждая дуга автомата A имеет прообраз в R, то
есть, любой гомоморфизм R в A полный. Эксперимент W можно понимать как част-
ный случай фрагмента автомата, частичный автомат RW , граф переходов которого
является ориентированным корневым деревом.
Пусть заданы класс F , автомат-эталон A и τ – бинарное отношение подобия
автоматов, которое определяет точность, необходимую при различении. Автомат R
(в общем случае частичный) называется представлением эталона A относительно F с
точностью τ , если R является таким фрагментом эталона A, что из R ≤ B следует,
что B ∈ τ(A) для любого B ∈ F . Далее рассматриваем случай, когда точность
является изоморфизмом. Множество всех представлений автомата A относительно
класса F обозначим как R(A,F ).
Пусть задан автомат Мили A из некоторого подкласса F n-полного класса Fn
всех автоматов с n состояниями и R – фрагмент автомата A. Фрагмент R может быть
фрагментом и некоторого другого автомата B ∈ F . Одна из основных задач теории
представлений состоит в том, чтобы указать такие условия, при которых A будет
единственным (с точностью до изоморфизма) в классе F автоматом, для которого
R является фрагментом, т.е. необходимые и достаточные условия, при которых R
есть представление автомата A относительно класса F . Эту задачу назовем задачей
характеризации представлений автомата относительно заданного класса. Решение
задачи характеризации часто позволяет оценить и сложность решения следующей
задачи, которую будем называть задачей распознавания представлений: предъяв-
ляется фрагмент R и автомат A из известного класса F ; необходимо определить,
является ли R представлением автомата A относительно класса F . Эти задачи рас-
сматриваются и для случая, когда в качестве представления выступает контрольный
эксперимент. Сложность задачи распознавания может служить косвенной оценкой
сложности определения момента завершения построения представления (или кон-
трольного эксперимента). Помимо этого, найденная характеризация позволяет в ря-
де случаев дать оценки сложности неизбыточных представлений (длины минималь-
ных экспериментов).
Как упоминалось выше, большинство рассматриваемых классов неисправностей
являются n-плотными классами для эталонов, где n – число состояний эталона. Их
можно описать как такие, которые содержат автоматы, полученные из приведенного
эталона A независимыми друг от друга перебросками дуг или изменениями отме-
ток дуг. Это влечет для представлений необходимое условие полноты фрагмента.
Точнее, пусть дуга u ∈ A, u = (s, x, y, t), u′=(s, x, y′, t′), причем y′ 6= y или t′ 6= t.
Обозначим B(u, u′) автомат, полученный из A заменой в нем дуги u дугой u′. То-
гда n-плотным классом для автомата A назовем всякий класс Fn(A) такой, что для
любой дуги u ∈ A в этом классе найдется автомат B(u, u′). Далее рассматриваем
82
Представления автоматов в локально определенных классах
случай, когда одношаговая функция выходов λ сохраняется при перебросках дуг.
Утверждение 1. Если A – приведенный автомат с n состояниями, то всякое
его представление R ∈ R(A,Fn(A)) является полным фрагментом автомата A.
Доказательство. Пусть R – представление A относительно Fn(A), и R не яв-
ляется полным фрагментом A, то есть, существует такой гомоморфизм ϕ R в A,
что некоторая дуга u не имеет прообраза в R при этом гомоморфизме. Так как
A− {u}=B(u, u′)− {u′}, то ϕ есть также гомоморфизм R в B(u, u′), то есть R есть
фрагмент B(u, u′). Но по модифицированной лемме о переброске дуги [3] автомат
B не изоморфен A, что противоречит тому, что R есть представление автомата A
относительно класса Fn(A). ¤
2. Локально определенные классы. Каждой паре (s, x) ∈ S ×X автомата A
поставим в соответствие некоторое множество состояний O(s, x), полагая при этом,
что состояния s и δ(s, x) принадлежат O(s, x). Обозначим совокупность таких мно-
жеств, соответствующих всевозможным парам (s, x) ∈ S×X, через O(A) и назовем
ее локализацией A. Локально определенным (посредством локализации O(A)) клас-
сом назовем класс LO(A) всех автоматов, полученных из автомата A заменой в нем
некоторой дуги (s, x, y, t) дугой (s, x, y, r), где r ∈ O(s, x), или множеством таких за-
мен. Из определения класса LO(A) следует, что он является n-плотным для A при
условии, что каждое множество из локализации O(A) содержит хотя бы два состо-
яния. Далее для простоты будем полагать, что это условие для рассматриваемых
локализаций выполняется.
Пусть R – фрагмент A, ϕ – некоторый гомоморфизм R в A. Дугу u=(s, x, y, t) ∈ A
назовем подтвержденной во фрагменте R при гомоморфизме ϕ, если во множестве
ее прообразов ϕ−1(u) найдется хотя бы одна дуга, конечная вершина которой не
является висячей. Такую дугу назовем подтвержденной в R, если она является под-
твержденной при любом гомоморфизме R в A.
Локально диагностируемым (по локализации O(A)) назовем автомат, в котором
для любой пары (s, x) ∈ S × X и для любых различных r, t ∈ O(s, x) верно нера-
венство λ(r, x′) 6= λ(t, x′) для любого x′ ∈ X. Заметим, что в общем случае, как
показывают примеры, локально диагностируемый автомат может быть неприведен-
ным.
Замечание. Для локально диагностируемого автомата A (по локализации O(A))
утверждение 1 остается справедливым и без требования приведенности эталона.
Действительно, в этом случае остается справедливой лемма о переброске дуги.
Переброска дуги (s, x, y, t) в одно из состояний r ∈ O(s, x) преобразует локально
диагностируемый автомат A в некоторый автомат B. Так как при переброске од-
ной дуги только для состояния s меняется множество λ2
s, а остальные автоматные
отображения высоты 2 остаются без изменений, то в автомате B число состояний, 2-
эквивалентных состоянию s, на единицу меньше, чем в исходном автомате A. Поэто-
му A и B не изоморфны, что оставляет справедливым доказательство утверждения
1 и в этом случае.
Далее нам понадобится понятие начального идентификатора состояния [3]. На-
83
В.А. Козловский, О.М. Копытова
чальным идентификатором состояния s называется такое порождаемое им множе-
ство Is вход-выходных слов, которое не порождается никаким другим состоянием
автомата. Высота идентификатора есть наибольшая из длин входящих в него слов.
Если идентификатор состоит из одного слова, он называется простым. Множество
всех состояний автомата A, имеющих начальные идентификаторы высоты 1, обо-
значим как S1
A, множество всех начальных идентификаторов автомата высоты 1 –
как I1
A.
Далее полагаем, что автомат-эталон A имеет непустое множество S1
A, и все со-
стояния автомата-эталона достижимы из состояний этого множества.
Пусть во фрагменте R ≤ A для любого состояния s ∈ S1
A найдется хотя бы одно
такое состояние r, что порожденное этим состоянием множество вход-выходных слов
длины 1 содержит хотя бы один начальный идентификатор высоты 1 состояния s.
Множество всех таких состояний фрагмента R обозначим S1
R.
Лемма 1. Пусть ϕ – гомоморфизм R в A, ψ – гомоморфизм R в B ∈ LO(A),
состояние r ∈ S1
R. Если для входного слова px x ∈ X, p не пустое слово, δR(r, px)
определено, то ϕ(δR(r, p))=ψ(δR(r, p)).
Доказательство. Так как переброска дуг сохраняет все эксперименты высоты
1, то множество начальных идентификаторов высоты 1 при перебросках дуг так-
же сохраняется. Поэтому в автомате-эталоне и в автомате B ∈ LO(A) множество
состояний S1
A также сохраняется, и ϕ(r)=ψ(r)=s, если I1
s ∩ I1
r 6= Ø, для любого
r ∈ S1
R. Пусть p=p1x1, x1 ∈ X. Если p1 пустое слово, то утверждение леммы сле-
дует из того, что состояние ϕ(δR(r, p)) принадлежит множеству O(s, x1), в котором
любые два состояния различаются по любому входному слову длины 1, а, значит, и
по слову x1. Так как эксперименты высоты 1 сохраняются в автомате B, и R есть
фрагмент автомата B, то ϕ(δR(r, p))=ψ(δR(r, p)). Пусть теперь p1 не пустое слово,
и ϕ(δR(r, p1))=ψ(δR(r, p1)). И в этом случае остаются в силе вышеприведенные рас-
суждения. ¤
На основании этой леммы мы можем однозначно разметить именами состояний-
образов из автомата A все состояния фрагмента R вдоль пути, определяемого словом
p из леммы 1, при любом гомоморфизме R в A. Как следует из леммы 1, эта разметка
не изменится и при любом гомоморфизме R в любой автомат B ∈ LO(A).
Теорема 1. Если все состояния автомата R достижимы из состояний S1
R,
и существует полный гомоморфизм R в автомат A, при котором подтверждена
каждая дуга автомата A, то R есть представление локально диагностируемого
по локализации O(A) автомата A относительно локально определенного класса
LO(A).
Доказательство. Пусть ϕ – полный гомоморфизм R в A, при котором подтвер-
ждена любая дуга автомата A. Так как все состояния R достижимы из состояний
множества S1
R, то во фрагменте для каждой дуги u = (s, x, y, t) автомата-эталона
существует ее прообраз u′ = (r, x, y, k), который принадлежит некоторому пути в
графе R, начинающемуся в одном из состояний множества S1
R и заканчивающемуся
в вершине, не являющейся концом прообраза. Такому пути соответствует слово, удо-
84
Представления автоматов в локально определенных классах
влетворяющее условиям леммы 1. Выполнив разметку состояний фрагмента вдоль
этого пути, как указано выше, получим разметку концов дуги u, ϕ(r)= s, ϕ(k)=t.
Проделав такую операцию разметки по всем дугам автомата A, определим по фраг-
менту в точности множество всех дуг эталона, что и доказывает теорему. ¤
Очевидно, что разметка состояний фрагмента R, описанная в теореме 1, опреде-
ляется ядром kerϕ = ϕ ◦ ϕ−1 гомоморфизма ϕ: состояния, принадлежащие одному
классу этой конгруэнции, получают имя состояния автомата A, в которое отобра-
жаются все состояния этого класса.
Непосредственным следствием теоремы является следующее утверждение.
Следствие 1. Эксперимент W является контрольным для автомата A отно-
сительно класса LO(A), если он является таким обходом автомата A из некото-
рого состояния r, r ∈ S1
R, что для каждого слова w = v(x, y) ∈ W дуга, покрываемая
парой (x, y) ∈ X × Y , подтверждена в эксперименте.
Если эксперимент простой, то следствие 1 требует, чтобы указанное в нем со-
стояние r обладало простым начальным идентификатором длины 1. Отсюда и из
оценок длины обходов автоматных графов вытекает
Следствие 2. Длина минимального простого контрольного эксперимента для
(A,LO(A)) не меньше mn + 1 и не больше (m + 1)n + 1/2(m− 1)n(n− 1), где n, m
– число состояний и входов автомата A соответственно, причем нижняя оценка
достижима.
Доказательство. Длина минимального обхода графа переходов автомата, как
известно, не меньше mn и не больше mn + 1
2(m− 1)n(n− 1). Дополнительное слово
длины 1 в обходе необходимо для подтверждения последней пройденной в экспери-
менте дуги, и, возможно, слово длины, не больше n−1 потребуется для того, чтобы
достичь состояния r, указанного в следствии 1, из заданного начального состояния.
Поэтому нижняя оценка достижима. ¤
Теорема 1 может быть усилена, если при выборе локализации потребовать сле-
дующее. Назовем окрестностью состояния s в автомате A множество всех его состо-
яний, достижимых из s по некоторому входу x, или из которых достижимо s по x.
Потребуем, чтобы любое множество O(s, x) ∈ O(A) содержало окрестность состо-
яния s. Класс автоматов по такой локализации обозначим LOC(A). Будем, как и
выше, полагать, что для эталона A множество S1
A 6= Ø, и во всякой компоненте связ-
ности автомата-эталона есть состояние из этого множества. Заметим также, что все
одноэлементные компоненты связности автомата A сохраняются во всех автоматах
класса LOC(A) при локализации, в точности совпадающей со множеством окрест-
ностей состояний. Поэтому и в данном случае полагаем, что каждое множество из
локализации содержит хотя бы два элемента.
Для всякой дуги u = (s, x, y, t) автомата A определим обратную дугу −u =
−(t, x, y, s), началом которой считаем t – конец прямой дуги, концом считаем со-
стояние s – начало прямой дуги, а ее отметку обозначаем как −(x, y). Полагаем,
что в пути по графу переходов автомата обратную дугу проходим в направлении,
противоположном ориентации соответствующей ей прямой дуги. Тогда полупуть
определим как последовательность из прямых и обратных дуг p = ∼ (s1, x1, y1, t2),
85
В.А. Козловский, О.М. Копытова
∼ (s2, x2, y2, t3) ,...,∼ (sk−1, xk−1, yk−1, tk), где ∼ указывает на прямую или обратную
ориентацию дуг, а соответствующее полупути слово из отметок прямых или обрат-
ных дуг – как полуслово, порожденное автоматом A в состоянии s. При указан-
ной локализации в локально диагностируемом автомате из равенств δ(s, x)=δ(t, x) и
λ(s, x)=λ(t, x) для любых x ∈ X следует равенство s=t. Поэтому в таком автомате
всякое полуслово w однозначно определяет полупуть из состояния s, порождающе-
го это полуслово, в состояние t, в котором оканчивается этот путь. В этом случае
будем писать s · w = t. Так как одношаговая функция выходов автомата-эталона
сохраняется в каждом автомате B ∈ LOC(A), то s · w однозначно определено в B
для любого полуслова w и состояния s. Учитывая это, можно сформулировать для
класса LOC(A) лемму, аналогичную лемме 1.
Лемма 2. Пусть ϕ – гомоморфизм R в A, ψ – гомоморфизм R в B ∈ LOC(A),
состояние r ∈ S1
R. Если для полуслова w(∼ (x, y)), w не пустое полуслово, r · w(∼
(x, y)) определено в R, то ϕ(r · w) = ψ(r · w).
Доказательство этого утверждения с учетом вышеприведенных замечаний почти
дословно повторяет доказательство леммы 1.
Будем, как и выше, полагать, что для эталона A множество состояний S1
A не
пусто, и во всякой компоненте связности автомата-эталона есть состояние из этого
множества. Заметим также, что все одноэлементные компоненты связности автома-
та A сохраняются во всех автоматах класса LOC(A) при локализации, в точности
совпадающей со множеством окрестностей состояний. Поэтому и в данном случае по-
лагаем, что каждое множество из локализации содержит хотя бы два элемента.Тогда
при замене в условиях теоремы 1 класса LO(A) на класс LOC(A) справедлива
Теорема 2. Автомат R есть представление локально диагностируемого по ло-
кализации O(A) автомата A относительно локально определенного класса LOC(A)
тогда и только тогда, когда R есть полный фрагмент A, такой, что в нем под-
тверждена каждая дуга автомата A.
Доказательство. Необходимость условий теоремы для R ∈ R(A,LOC(A)) фак-
тически следует из утверждения 1. Дополнительное требование подтвержденности
каждой дуги следует из того, что в противном случае неподтвержденная дуга может
быть переброшена в любое состояние соответствующей окрестности, и для получен-
ного автомата R также будет фрагментом.
Доказательство достаточности, учитывая лемму 2 и принятые ограничения, по-
вторяет доказательство теоремы 1 (с соответствующими заменами слов и путей на
полуслова и полупути). ¤
При условии наличия в автомате простого начального идентификатора длины
1, как прямое следствие теоремы 2, усиливается и аналог следствия 1.
Следствие 3. Простой эксперимент W автомата A является контрольным
для (A,LOC(A)) тогда и только тогда, когда он является таким обходом авто-
мата A, что если w = v(x, y) ∈ W , то дуга, покрываемая парой (x, y) ∈ X × Y ,
подтверждена.
Следствие 2 в этом случае также можно усилить.
86
Представления автоматов в локально определенных классах
Следствие 4. Длина минимального простого контрольного эксперимента для
(A,LOC(A)) не меньше mn + 1 и не больше mn + 1/2(m − 1)n(n − 1) + 1, где n,
m – число состояний и входов автомата A соответственно, причем обе оценки
достижимы.
Его справедливость следует из выполнения условий следствия 3 для любого об-
хода автомата с подтверждением последней пройденной дуги и оценок длины крат-
чайших обходов графов переходов автоматов.
Заключение. Из полученных характеризаций следует полиномиальность зада-
чи распознавания контрольных экспериментов для таких классов в отличие от дру-
гих n-плотных классов (n-полного, групповых автоматов, без потери информации и
др.), для которых эта задача является NP -полной даже при условии максимального
разнообразия в поведении эталона [4]. Из них же следует, что полученные оценки
длины простых экспериментов сложности не могут быть улучшены для n-плотных
классов, получаемых произвольными перебросками дуг.
1. Bhattacharyya A. Checking experiments on sequential machines. – New York: J. Wiley and Sons,
1989. – 155c.
2. Козловский В.А., Копытова О.М. Представления автоматов относительно m-плотных клас-
сов // Матер. VIII Межд. семинара "Дискретная математика и ее приложения" (Москва, 2–6
февраля 2004г.). – М.: Изд.-во МГУ. – С.277-280.
3. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов. – Киев: Наукова думка,
2004. – 246с.
4. Козловский В.А. Локальные неисправности автомата и их обнаружение // Математические
вопросы кибернетики (под ред. С.В.Яблонского). – М.: Наука, 1991, вып.3. – С.167-186.
5. Козловский В.А., Копытова О.М. Контрольные эксперименты в локально определенных клас-
сах // Материалы IX Международного семинара "Дискретная математика и ее приложения",
посв. 75-летию со дня рожд. акад. О.Б.Лупанова (Москва, МГУ, 18-23 июня 2007г.) / Под ред.
О.М.Касим-Заде. – М.: Изд-во мех.-мат. ф-та МГУ, 2007. – С.322-324.
Ин-т прикл. математики и механики НАН Украины, Донецк
kozlovskii@iamm.ac.donetsk.ua
Получено 11.09.08
87
содержание
Том 17
Донецк, 2008
Основан в 1997г.
|
| id | nasplib_isofts_kiev_ua-123456789-20012 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1683-4720 |
| language | Russian |
| last_indexed | 2025-12-07T13:15:20Z |
| publishDate | 2008 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Козловский, В.А. Копытова, О.М. 2011-05-20T07:36:52Z 2011-05-20T07:36:52Z 2008 Представления автоматов в локально определенных классах / В.А. Козловский, О.М. Копытова // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 80-87. — Бібліогр.: 5 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/20012 519.7 ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики НАН Украины Представления автоматов в локально определенных классах Article published earlier |
| spellingShingle | Представления автоматов в локально определенных классах Козловский, В.А. Копытова, О.М. |
| title | Представления автоматов в локально определенных классах |
| title_full | Представления автоматов в локально определенных классах |
| title_fullStr | Представления автоматов в локально определенных классах |
| title_full_unstemmed | Представления автоматов в локально определенных классах |
| title_short | Представления автоматов в локально определенных классах |
| title_sort | представления автоматов в локально определенных классах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/20012 |
| work_keys_str_mv | AT kozlovskiiva predstavleniâavtomatovvlokalʹnoopredelennyhklassah AT kopytovaom predstavleniâavtomatovvlokalʹnoopredelennyhklassah |