The accepting power of finite automata over groups

被引：0

作者：

Mitrana, V ^{[1
]}

Stiebe, R ^{[1
]}

机构：

[1] Univ Bucharest, Fac Math, Bucharest 70109, Romania

来源：

NEW TRENDS IN FORMAL LANGUAGES | 1997年 / 1218卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Some results from [2], [5], [6] are generalized for finite automata over arbitrary groups. The accepting power is smaller when abelian groups are considered, in comparison with the non-abelian groups. We prove that this is due to the commutativity. Each language accepted by a finite automaton over an abelian group is actually a unordered vector language. Finally, deterministic finite automata over groups are investigated.

引用

页码：39 / 48

页数：10

共 8 条

[1] Dassow J., 2012, Regulated Rewriting in Formal Language Theory
[2] DASSOW J, 1996, FINITE AUTOMATA FREE
[3] GINSBURG S, 1969, MEM AM MATH SOC, V87, P1
[4] Ginsburg S., 1975, ALGEBRAIC AUTOMATA T
[5] Greibach S. A., 1978, Theoretical Computer Science, V7, P311, DOI 10.1016/0304-3975(78)90020-8
[6] Ibarra O. H., 1976, Theoretical Computer Science, V2, P271, DOI 10.1016/0304-3975(76)90081-5
[7] Paun Gh., 1980, REV ROUMAINE MATH PU, V6, P911
[8] Rotman J. J., 1995, Grad. Texts in Math., V148

← 1 →