Представления автоматов в локально определенных классах

Saved in:
Bibliographic Details
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