|
Prikladnaya Diskretnaya Matematika, 2011, Number 2(12), Pages 73–76
(Mi pdm278)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Applied Automata Theory
Skeleton automata
V. N. Salii Saratov State University named after N. G. Chernyshevsky, Saratov, Russia
Abstract:
A skeleton automaton is an automaton in which the relation of mutual accessibility of states is the identity relation. We prove that automata that admit a regular enumeration of states are exactly skeleton automata. It is shown how for a given automaton one can construct an automaton with minimal number of states that has the same subautomata lattice, and is necessarily a skeleton automaton. A procedure is proposed to obtain a skeleton automaton from a given automaton by removal of minimal number of arcs in its transition diagram.
Keywords:
automaton, strongly connected automaton, skeleton automaton, regular enumeration of states, subautomata lattice.
Citation:
V. N. Salii, “Skeleton automata”, Prikl. Diskr. Mat., 2011, no. 2(12), 73–76
Linking options:
https://www.mathnet.ru/eng/pdm278 https://www.mathnet.ru/eng/pdm/y2011/i2/p73
|
Statistics & downloads: |
Abstract page: | 308 | Full-text PDF : | 72 | References: | 40 | First page: | 1 |
|