On directable nondeterministic trapped automata

Imreh Balázs and Imreh Csanád and Ito Masami: On directable nondeterministic trapped automata. In: Acta cybernetica, (16) 1. pp. 37-45. (2003)

[thumbnail of cybernetica_016_numb_001_037-045.pdf]
Cikk, tanulmány, mű

Download (872kB) | Preview


A finite automaton is said to be directable if it has an input word, a directing word, which takes it from every state into the same state. For nondeterministic (n.d.) automata, directability can be generalized in several ways. In [8], three such notions, D1-, D2-, and D3-directability, are introduced. In this paper, we introduce the trapped n.d. automata, and for each i = 1,2,3, present lower and upper bounds for the lengths of the shortest Di-directing words of n-state Di-directable trapped n.d. automata. It turns out that for this special class of n.d. automata, better bounds can be found than for the general case, and some of the obtained bounds are sharp.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2003
Volume: 16
Number: 1
ISSN: 0324-721X
Page Range: pp. 37-45
Language: English
Place of Publication: Szeged
Event Title: Conference for PhD Students in Computer Science (3.) (2002) (Szeged)
Related URLs: http://acta.bibl.u-szeged.hu/38515/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 44-45. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 14. 15:38
URI: http://acta.bibl.u-szeged.hu/id/eprint/12707

Actions (login required)

View Item View Item