• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Commutative Nondeterministic Directable Automata

Balazs Imreh, Masami Ito, Magnus Steinby, On Commutative Nondeterministic Directable Automata. In: Grammars and Automata for String Processing, Topics in Computer Mathematics 9, 141–150, Taylor & Francis, 2003.

Abstract:

In [8] an input word $w$ of a nondeterministic automaton (nda) $A$ was called:
(1) D1-directing if the set of states $aw$ in which $A$ may be after reading $w$ is the same singleton set ${b}$
for all initial states $a$;
(2) D2-directing if the set $aw$ is the same for every initial state $a$;
(3) D3-directing if the some state $b$ appears in every set $aw$.
Here we consider these notions for commutative nda. Commutativity is a very strong assumption which virtually eliminates
the distinction between general nda and complete nda (cnda). Moreover, the sets of Di-directing words of a given nda are
essentially of the same form in all six cases considered. We also give bounds for the maximal lengths of minimum-length Di-
directing words of an nda or cnda (i = 1,2,3).

BibTeX entry:

@INBOOK{cImItSt03a,
  title = {On Commutative Nondeterministic Directable Automata},
  booktitle = {Grammars and Automata for String Processing},
  author = {Imreh, Balazs and Ito, Masami and Steinby, Magnus},
  volume = {9},
  series = {Topics in Computer Mathematics},
  publisher = {Taylor & Francis},
  pages = {141–150},
  year = {2003},
  keywords = {finite automata, directing words, nondeterministic automata},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication