2 ω-finite automata and sets of obstructions of their languages.

Autor: Melnikov, B. F.
Zdroj: Journal of Applied Mathematics & Computing; Sep1999, Vol. 6 Issue 3, p565-574, 10p
Abstrakt: Nondeterministic finite Rabin-Scott's automata without initial and final states (2ω-FA) are considered. In this paper, they are used to define so called sets of obstructions, used also in various algebraic systems, and to consider similar problems for the formal languages theory. Thus, we define sets of obstructions of languages (or, rather, 2ω-languages) of such automata. We obtain that each 2ω-language defined by 2 ω-FA has the set of obstruction being a regular language. And, vice versa, for each regular languageL (containing no proper subword of its another word), there exists a 2ω-FA havingL as the set of obstructions. [ABSTRACT FROM AUTHOR]
Databáze: Complementary Index