Automata accepting primitive words |
| |
| Authors: | M Ito M Katsura H J Shyr S S Yu |
| |
| Institution: | 1. Faculty of Science, Kyoto Sangyo University, 603, Kyoto, Japan
2. Institute of Applied Mathematics, National Chung-Hsing University, 400, Taichung, Taiwan
|
| |
| Abstract: | LeA be an automaton whose set of inputs equalsX (|X|≧2) and whose cardinality of the set of states equalsn (n≧2), and letQ be the set of all primitive words overX. ByT(A) we denote the language accepted byA. In this paper, we give the following results:
| (1) |
T(A)⋔Q≠ ⊘ if and only ifA accepts a primitive wordy withlg(y)≦3n−3, wherelg(y) means the length ofy.
|
| (2) |
|T(A)⋔Q|=∞ if and only ifA accepts a primitive wordy withn≦lg(y)≦3n−3, where |T(A)⋔Q| means the cardinality ofT(A)⋔Q.
|
Moreover, we deal with the case |T(A)⋔Q|<∞ and obtain upper bounds on the cardinalities ofT(A)⋔Q and of some language related toT(A). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
