维普资讯 http://www.cqvip.com 第２５卷第１期 广西师范大学学报：自然科学版 Ｖｏ１．２５ Ｎｏ．１ ２００７年３月 Ｊｏｕｒｎａｌ ｏｆ Ｇｕａｎｇｘｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ Ｍａｒ．２００７ 有限群自动机的若干环论与图论性质 阎航宇，易忠，邓培民 （广西师范大学数学科学学院，广西桂林５４１００４） 摘要：通过研究有限群自动机的关联环和导图来刻画有限群自动机，给出了有限群自动机不可约和不可分 的一些判别法则。 关键词：有限群自动机；关联环；导图；不可约；不可分 中图分类号：ＴＰ３０１．１ 文献标识码：Ａ 文章编号：１００１—６６００（２００７）０１—００３０—０４ 有限群自动机是代数自动机理论的一个较新的研究方向，代数自动机理论已有不少经典的专著［】ｑ］。 已有一些论文通过群和矩阵这些代数工具研究了有限自动机的一些问题［４叫。。。文献［４］研究了一类有限 群自动机的关联环的Ｊａｃｏｂｓｏｎ根，描述了相应的有限群自动机的结构。从文献ｒ４－ｉ中可以看到关联环是一 个研究有限群自动机的有力工具，本文通过研究关联环的环论性质给出了有限群自动机的一些性质。不可 约和不可分是两个很重要的代数概念，有限群自动机作为代数系统自然地要涉及不可约和不可分的研究， 本文利用有限群自动机的导图的图论性质给出了有限群自动机的不可约和不可分的一些判别法则。 １基本概念与记号 定义１有限群自动机是一个三元组Ｍ一（Ｑ，Ｇ， ），Ｑ是有限状态集，Ｇ是输入字母集为有限群， Ｑ×Ｇ￣Ｑ是转移关系，且满足３（３（ｑ，ｇ）， ）￣－３（ｑ， ） Ｑ，ＶｑＥ Ｑ，ｇ，ｈ∈Ｇ。记 （ｇ，ｇ）一｛ｒＥＱ ｆ（ｇ，ｇ，ｒ） ∈ ），简记为ｑｇ。令Ｑ１ Ｑ，Ｇ１ Ｇ，记３（Ｑ１，Ｇ１）一｛ｒＥＱ ｌ（ｇ１，ｇｌ，ｒ）∈ ，ｑ１∈Ｑ ，ｇ１∈Ｇ１），简记为Ｑ１Ｇ１。 定义２设Ｆ—ＧＦ（户 ）是阶为Ｐ 的有限域，记ＩＭ（Ｆ）为有限群自动机。Ｍ一（Ｑ，Ｇ， ）关于Ｆ的关联 环，它是Ｆ上以ＴＭ为基的向量空间，ＴＭ ｛（ｇ；ｇ，ｑ ）ｌｇ∈Ｇ，ｑ∈Ｑ，ｑ ∈ （ｇ，ｇ）），乘法按照分配律和以下 规则给出： （ｇ１；ｇ１，ｇ ）．（ｇ２；ｇ２，ｇ ）一ｆ １ ｇ ＂，０，ｑ＇ｘｇ≠２， ｑｚ， ：＝：ｇ２， ｒ．（ｇ；ｇ，ｇ，）一（ｇ；ｇ，ｇ，）．ｒ， Ｖｇ，ｇｌ，ｇｚ∈Ｇ，ｑｌ，ｑ ，ｑｚ，ｑ ，ｑ，ｑ ∈Ｑ。 定义３ 定义厂： （Ｆ）一坛（Ｆ［Ｇ］），令ｌＱ ｌ— ，若ｎ＞Ｏ，不妨把Ｑ中的元素看成是１，２，…， ， 厂（ （ ； ，ｑ ））一 （ ） ；若 一０，厂（０）一０；易知ｆ是同构嵌入。 注：本文中涉及的其他概念和记号均参考文献［１１］。 ２ 有限群自动机的若干环论与图论性质 先通过研究关联环的一些代数性质给出了有限群自动机的一些刻画。 收稿Ｅｔ期：２００６—０９—２７ 基金项目：国家自然科学基金资助项目（６０４７３００５）；教育部“优秀青年教师资助计划”资助项目（２００２—４０）；广西自然科 学基金资助项目（０６４００６１） 作者简介：阎航宇（１９８１一），男，浙江宁波人，广西师范大学硕士研究生；易忠（１９６１一），男，湖南长沙人，广西师范大学 教授，博士。 维普资讯 http://www.cqvip.com 第１期 阎航宇等：有限群自动机的若干环论与图论性质 ３１ 定理１设Ｑ是非空有限集，ｌ Ｑ ｌ—ｎ，Ｑ中的元素记为１，２，…，ｎ，Ｇ是有限群，则唯一存在有限群自 动机Ｍ。一（Ｑ，Ｇ，３０）使得厂是同构，其中厂是定义３中的映射。 推论１设 一（Ｑ，Ｇ， ）是有限群自动机，则ｆ是同构的充分必要条件为Ｖｇ∈Ｑ，ｇ∈Ｇ，有３（ｑ，ｇ）一 Ｑ。 定理２设 一（Ｑ，Ｇ， ）是有限群自动机，ｅ为Ｇ的单位元，则ＩＭ（Ｆ）是幂零代数的充分必要条件为 ｑ ｑｅ，Ｖｑ∈Ｑ。 证明 假设存在ｑ∈Ｑ，使得ｑ∈ｑｅ，则有（ ；ｇ，ｇ）∈ＴＭ，从而Ｖ，２∈Ｎ＋，都有（ ；ｇ，ｇ） 一（ ；ｇ，ｇ）≠ ０。所以ＩＭ（Ｆ）不是幂零代数，这与题意相矛盾。故ｑ ｑｅ，Ｖｑ∈Ｑ。 假设ＩＭ（Ｆ）不是幂零代数，则Ｖ志∈Ｎ＋，都有ａ …，ａ从∈ＩＭ（Ｆ），使得 … ≠０。那么由ＩＭ（Ｆ） 的定义可知，存在（ ； ，ｑｌ ），…，（ｇ从；ｇ ｇ ２一ｇ＾３，…，ｑｌ＾一１－＝ｑｋｋ。 ）∈ＴＭ，使得（ｇｋ ；ｑｋ ，ｑｌ１）…（ｇｋｋ；ｑｋｋ， ）≠ｏ，所以ｑｌ 一 ２， 令ｌＱ ｌ一，２，取志一，２＋１，则对于ｑ（计１）ｌ，…，ｇ（计１）（计 ）必存在两个相等。不妨记为ｑ（计１）ｌ—ｇ（计Ⅲ一ｇ， ＜ ，ｉ，Ｊ∈｛１，…，，２＋１），ｇ（ ＋１） …ｇ ＋１）（，一１）一ｇ，那么有： （ｇ ＋１） ；ｇ ＋１） ，ｇ ＋１） ）…（ｇ（ ＋１）（，一１）；ｇ ＋１）（，一１），ｇ ＋１）（，一１））一（ｇ；ｇ ＋１） ，ｇ（ ＋１），）一（ｇ；ｇ，ｇ）。 令ｌＧ ｌ— ，则有ｇ 一 ，所以由（ｇ；ｇ，ｇ）∈ＴＭ可知：（ｇ；ｇ，ｇ） 一（ｇ ；ｇ，ｇ）一（ ；ｇ，ｇ）∈ＴＭ。所以有ｑ∈ ，这与题意相矛盾。故ＩＭ（Ｆ）是幂零代数。证毕。 推论２设 一（Ｑ，Ｇ， ）是有限群自动机，ｅ为Ｇ的单位元，则ＩＭ（Ｆ）是诣零代数的充分必要条件为 ｑ ｑｅ，ＶｑＥＱ。 证明因为ＩＭ（Ｆ）是有限维结合代数，所以ＩＭ（Ｆ）是诣零代数当且仅当ＩＭ（Ｆ）是幂零代数［１引。所以根 据定理２可知，结论成立。证毕。 定理３设 一（Ｑ，Ｇ， ）是有限群自动机，ＩＭ（Ｆ）≠０，则ＩＭ（Ｆ）是无零因子环的充分必要条件为Ｇ一 ｛ｅ），且 ｑ。∈Ｑ，使得 一｛（ ；ｇ。，ｑｏ））。 证明 因为ＩＭ（Ｆ）≠Ｏ，所以ｒ，Ｍ≠ 。设（ｇ；ｇ ，ｑ２）∈ＴＭ，则由ＩＭ（Ｆ）是无零因子环可知：（ｇ；ｇ ， ｑ２）（ｇ；ｇ ，ｑ２）≠Ｏ，所以ｑ 一ｇ２。所以ｒ，Ｍ中的元素必为形式（ｇ ；ｇ，ｇ），ｑ∈Ｑ，ｇ ∈Ｇ。 设（ｇ ；ｇ：，ｑ：），（ｇ ；ｇ ，ｑ ）∈ＴＭ，因为ＩＭ（Ｆ）是无零因子环，所以（ｇ ；ｇ ，ｑ ）（ｇ ；ｇ ，ｑ ）≠Ｏ。所以ｑ：一 ｑ 。记ｅ为Ｇ的单位元，又因为ｑｅ：／： ∞ｇｇ≠ ，ＶｇＥＧ，ｑ∈Ｑ。所以 ｑｏ∈Ｑ，ＴＭ＝｛（ｇ；ｇｏ，ｑｏ）ｌ ＶｇＥＧ）。 现证ｌＧ ｌ一１。假设ｌ Ｇ ｌ≠１，则存在ｇＥＧ，Ｄ（ｇ）一点＞１。因为ｅ，ｇ，…，ｇ卜 互不相同，显然有： （ ；ｇｏ，ｑｏ）一（ｇ；ｇｏ，ｑｏ）≠０，（ ；ｑｏ，ｑｏ）＋（ｇ；ｑｏ，ｑｏ）＋…＋（ ＿。；ｑｏ，ｇｏ）≠０。 但有（（ ；ｇ。，ｑｏ）一（ｇ；ｇ。，ｑｏ））（（ｅ；ｇ。，ｑｏ）＋（ｇ；ｑｏ，ｑｏ）＋…＋（ ＿。；ｇｏ，ｑｏ））一０，这与题意相矛盾。所以假设 不成立，Ｇ一｛ｅ）。 由题意知ＩＭ（Ｆ）的元素必为ｋ（ ；ｇ。，ｑ。），ｅ∈Ｇ，ｋ∈Ｆ，所以Ｖａ， ∈ＩＭ（Ｆ），口， ≠０，必有ｋ ，ｋ２≠０， ｋ１，ｋ２∈Ｆ，使得ａ＝ｋ１（ ；ｇｏ，ｑｏ）， 一点２（ ；ｇｏ，ｑｏ）。所以口 一（志１ｋ２）（ｅｌｑｏ，ｑｏ）≠Ｏ。所以ＩＭ（Ｆ）是无零因子环。 证毕。 关联环由基完全确定，下面研究基ｒ，Ｍ。 命题１设 一（Ｑ，Ｇ， ）是有限群自动机，且ｒ，Ｍ≠ ，ｅ是Ｇ的单位元，则ＴＭ是幺半群的充分必要 条件为 ｇ。∈Ｑ，使得ＴＭ一｛（ｇ；ｇ。，ｑｏ）ｌ ＶｇＥ Ｇ）。 推论３设 一（Ｑ，Ｇ， ）是有限群自动机，若存在ｑ。∈Ｑ，使得ＴＭ ｛（ｇ；ｇｏ，ｑｏ）Ｊ ＶｇＥＧ），则ＩＭ（Ｆ）是 含幺环。 推论３的逆命题不一定成立。如Ｑ一｛ｑ ，ｑ２），Ｇ一｛ｅ），３（ｑ ， ）－＝ｑ ，ｉ一１，２。则有ＴＭ｛（ ；ｇ ，ｑ ），（ ； ｑ２，ｑ２）），容易验ｉｉＥ（ｅ；ｇ ，ｑ１）＋（ｅ；ｇ２，ｑ２）是ＩＭ（Ｆ）的幺元，但ＴＭ不是ＴＭ ｛（ｇ；ｇｏ，ｑｏ）ｌ ＶｇＥＧ）这种形式。 定理４设 一（Ｑ，Ｓ， ）是有限半群自动机，若ＩＭ（Ｆ）是单环，则 的导图是连通的。 一般情况下，定理４的逆命题不一定成立。如：取Ｑ一｛ｑ ，ｑ：），Ｓ一｛ｓ），定义３（ｑ ，ｓ）一｛ｑ ，ｑｚ），３（ｑｚ，ｓ） 一 ，Ｓ是半群，易验证 一（Ｑ，Ｓ， ）是有限半群自动机， 的导图是连通的，但ＩＭ（Ｆ）不是单环，因为容 维普资讯 http://www.cqvip.com 广西师范大学学报：自然科学版 第２５卷 易验证Ｆ（ｓ；ｇ ，ｑｚ）是ＩＭ（Ｆ）的非平凡理想。 下面给出有限群自动机的不可约和不可分的一些判别法则。 命题２设 一（Ｑ，Ｇ， ）是有限群自动机，且ｌＱ ｌ＞１，则Ｍ是不可约的充分必要条件为Ｖｇ∈Ｑ，ｑＧ Ｕ ｛ｑ）一Ｑ。 命题３设 一（Ｑ，Ｇ， ）是有限群自动机，且ＪＱ ｌ＞１，则 是不可约的当且仅当 是连接的。 命题４设 一（Ｑ，Ｇ， ）是有限群自动机，且ｌＱ ｌ＞１，则Ｍ是不可约的充分必要条件为 不存在真 稳定子集。 定理５设 一（Ｑ，Ｇ， ）是有限群自动机，且ＪＱ ｆ＞１，则下列条件彼此等价：① 是不可约的；②Ｖｇ ∈Ｑ，ｑＧＵ｛ｑ）一Ｑ；③Ｍ是连接的；④Ｍ不存在真稳定子集。 定理６设 一（Ｑ，Ｇ， ）是有限群自动机，ｌＱ ｌ＞１，则Ｍ是不可分的当且仅当 是弱连通的。 证明 假设 不是弱连通的，记 是ＤＭ的基图，则Ｗ不是连通的，那么 至少有两个连通分 支，任取 的两个连通分支为 （ 一１，２）。设 的顶点集为Ｑ ，因为 是 的连通分支，所以 一 （Ｑ ，Ｇ， ｌＱ ×Ｇ×Ｑ ）是有限群自动机，Ｑ＼Ｑ ≠ ，（Ｑ＼Ｑ ）Ｇ Ｑ＼Ｑ 。所以 一（Ｑ＼Ｑ ，Ｇ， ｌ（Ｑ＼Ｑ ）×Ｇ× （Ｑ＼Ｑ ））是有限群自动机。 又因为Ｑ ≠ ，所以根据定义可知， 是可分的，这与“ 是不可分的”相矛盾。所以假设不成立。故 是弱连通的。 假设 是可分的，则存在Ｑ ，Ｑ Ｑ，Ｑ ，Ｑ ≠Ｑ，满足Ｑ ＵＱ ＝Ｑ，Ｑ ＮＱ 一 ，且 ＝（Ｑ ，Ｇ， ｆＱ ×Ｇ×Ｑ ）是有限群自动机，ｉ一１，２。又因为ＪＱ ｌ＞１，所以Ｑ ≠ ，Ｑ ≠ ，Ｑ Ｇ Ｑ ，Ｑ Ｇ Ｑ 。所以ＤＭ 的基图不是连通的，即 不是弱连通的，这与“ 是弱连通的”相矛盾，所以假设不成立，从而 是不可分 的。证毕。 定理７设 ＝（Ｑ，Ｇ， ）是有限群自动机，且Ｑ≠ ，则Ｍ可以分解为一些不可分的有限群自动机的 并。 证明 设Ｄ是由 一（Ｑ，Ｇ， ）导出的有向赋值图， 是Ｄ的基图。由于 是有限图，从而 可以分 解为一些连通分支的并［１ 。不妨设Ｗ＝Ｗ Ｕ…Ｕ ，其中 （ 一１，…，ｎ）是Ｗ的不相交的连通分支。设 的顶点集合为Ｑ ，令 一（Ｑ ，Ｇ， ｌ Ｑ ×Ｇ×Ｑｆ），因为 是 的一个连通分支，所以有 是有限群 自动机，且 是 的极大弱连通分支。由 是弱连通的可知， 是不可分的。显然有 —Ｖ ，故 可 以分解为一些不可分的有限群自动机的并。 下面给出证明当有限群自动机是幺式时，有限群自动机的三个概念“连通 弱连通 连接”是等价的。 引理１设 ＝（Ｑ，Ｇ， ）是幺式有限群自动机， 为Ｇ的单位元，对于ｑ ，ｑ ＥＱ，则ｑ 可达ｑ 的充分 必要条件为ｑ 可达ｑ 。 命题５设 一（Ｑ，Ｇ， ）是幺式有限群自动机，则Ｍ是连通的当且仅当 是连接的。 命题６设 一（Ｑ，Ｇ， ）是幺式有限群自动机，则Ｍ是连通的充分必要条件为 是弱连通的。 定理８设 ＝（Ｑ，Ｇ， ）是幺式有限群自动机，则下列条件彼此等价：① 是连通的；② 是连接的； ③ 是弱连通的。 最后用有向赋值图刻画有限群自动机的一个结果作为结束。 定理９设 一（Ｑ ，Ｇ， ）是有限群自动机，ｉ一１，２，则Ｍ 与 的导图与 的导图赋值同构。 证明记 的导图为Ｄ ＝（Ｑ ，Ｅ ，Ｇ）， 一１，２。 在Ｇ上等价的充分必要条件为 因为 与 ｚ在Ｇ上等价，所以存在双射 ：Ｑ 一Ｑｚ，使得 （ｇ ｇ）＝ （ｇ ）ｇ，Ｙｑ ＥＱ ，ｇＥＧ。要证 Ｄ１与Ｄ２赋值同构，只需证（ｇ１，ｑｉ） ＥＥ１甘（ （ｇ１）， ｇ ）） ＥＥ２，ＶｇｌＥＱｌ，ｇＥＧ。 若（ｑｌ，ｑｉ） Ｅ Ｅ１，则有ｑｉ Ｅ ｑｌｇ。所以 （ｇ：）Ｅ （ｇｌｇ）一 （ｇ１）ｇ。所以（ （ｇ１）， （ｇｉ）） Ｅ Ｅ２。若（ （ｇ１）， （ｇ ）） ＥＥ２，则有 （ｇ ）Ｅ （ｇ１）ｇ— （ｇｌｇ）。又因为 是双射，所以ｑ：Ｅ ｑｌｇ。所以（ｇｌ，ｇｉ） Ｅ Ｅｌ。所以（ｇｌ， ｑｉ） ∈Ｅｌ甘（ （ｇ１）， （ｇｉ）） ＥＥ２，ＶｑｌＥＱ１，ｇＥＧ。 维普资讯 http://www.cqvip.com 第１期 阎航宇等：有限群自动机的若干环论与图论性质 ３３ 若Ｄ 与Ｄ 赋值同构，则存在双射 ：Ｑ 一Ｑ ，使得（ｇ ，ｑ：） ∈Ｅ 学（ （ｇ ）， （ｇ：）） ∈Ｅｚ，Ｙｑ ∈Ｑ ， ｇＥＧ。所以 （ｇ１）ｇ一 （ｇ１ｇ），Ｙｑ１∈Ｑ１，ｇＥ Ｇ。故Ｍ１与Ｍ２在Ｇ上等价。证毕。 参考文献： ［１］ ＨＯＬＣＯＭＢＥ Ｗ Ｍ Ｌ．Ａｌｇｅｂｒａｉｃ ａｕｏｔｍａｔａ ｔｈｅｏｒｙ［Ｍ］．Ｃａｍｂｒｉｄｇｅ：Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９８２． ［２］ ＥＩＬＥＮＢＥＲＧ Ｓ．Ａｕｔｏｍａｔａ，ｌａｎｇｕａｇｅｓ，ａｎｄ ｍａｃｈｉｎｅｓ：ｖｏｌｕｍｅ Ａ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ，１９７４． ＬＥＮＢＥＲＧ Ｓ．Ａｕｔｏｍａｔａ，ｌａｎｇｕａｇｅｓ，ａｎｄ ｍａｃｈｉｎｅｓ：ｖｏｌｕｍｅ Ｂ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ，１９７６． ［３］ ＥＩ［４］ ＫＥＬＡＲＥＶ Ａ Ｖ Ｏ．Ｇｒｏｕｐ ａｕｔｏｍａｔａ ｏｖｅｒ ｆｉｎｉｔｅ ｆｉｅｌｄｓ［Ｊ］．Ｆｉｎｉｔｅ Ｆｉｅｌｄｓ ａｎｄ Ｔｈｅｉｒ Ａｐｐｌｉｃａｔｉｏｎ，２００４，１０：６５—７１． ｏｕｐ ａｃｔｉｏｎｓ ｏｎ ｓｅｔｓ ａｎｄ ａｕｔｏｍａｔａ ｔｈｅｏｒｙｌ，Ｊ］．Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔｉｏｎ，２０００，１１３：２８９— Ｅ５］ ＬＡＳＺＬＯ Ａ Ｖ．Ｇｒ３Ｏ４． ［６］ ＮＩＣＡＵＤ Ｃ．Ｒａｎｄｏｍ ｇｒｏｕｐ ａｕｔｏｍａｔａＩ＇Ｃ］／／ＣＨＹＺＡＫ Ｆ．Ａｌｇｏｒｉｔｈｍｓ ｓｅｍｉｎａｒ １９９９—２０００．Ｌｅ Ｃｈｅｓｎａｙ，Ｆｒａｎｃｅ：ＩＮＲＩＡ， ２０００：２７—３０． ＴＲＡＭＡ Ｖ，ＳＴＩＥＢＥ Ｒ．Ｅｘｔｅｎｄｅｄ ｆｉｎｉｔｅ ａｕｔｏｍａｔａ ｏｖｅｒ ｇｒｏｕｐｓｌ－Ｊ］．Ｄｉｓｃｒｅｔｅ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，２００１，１０８：２８７— ［７］ ＭＩ３００． ［８］ ＤＡＳＳＯＷ Ｊ，ＭＩＴＲＡＮＡ Ｖ．Ｆｉｎｉｔｅ ａｕｔｏｍａｔａ ｏｖｅｒ ｆｒｅｅ ｇｒｏｕｐｓ －ｌＪ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ａｌｇｅｂｒａ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎ， ２０００，１０（６）：７２５—７３７． ［９］ 曹锋，邓培民，易忠．关于Ｍｏｏｒｅ自动机可逆性的一些结果ｌ－Ｊ］．广西师范大学学报：自然科学版，２００３，２１（４）：４４—４７． ［１Ｏ］ 文毅玲，邓培民，易忠．有限自动机化合的一些结果ｌ－Ｊ］．广西师范大学学报：自然科学版，２００５，２３（２）：２７—３０． ［１１］ 阎航宇．有限群自动机的研究及其推广ｌ－Ｄ］．桂林：广西师范大学数学科学学院，２００６． ［１２］ 刘绍学．环与代数［Ｍ］．北京：科学出版社，１９８３． Ａ，默蒂Ｕ Ｓ Ｒ．图论及其应用ｌ－Ｍ］．北京：科学出版社，１９８４． ［１３］ 邦迪ＪＳｏｍｅ Ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ Ｒｉｎｇ Ｔｈｅｏｒｙ Ａｎｄｇｒａｐｈ Ｔｈｅｏｒｙ ｏｎ Ｆｉｎｉｔｅ Ｇｒｏｕｐ Ａｕｔｏｍａｔａ ＹＡＮ Ｈａｎｇ－ｙｕ，ＹＩ Ｚｈｏｎｇ，ＤＥＮＧ Ｐｅｉ—ｍｉｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃａｌ Ｓｃｉｅｎｃｅ，Ｇｕａｎｇｘｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕｉｌｉｎ ５４１００４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｍａｉｎｌｙ ｄｅｓｃｒｉｂｅｓ ｆｉｎｉｔｅ ｇｒｏｕｐ ａｕｔｏｍａｔａ ｔｈｒｏｕｇｈ ｔｈｅ ｓｔｕｄｙ ｏｆ ｔｈｅｉｒ ｉｎｃｉｄｅｎｃｅ ｒｉｎｇｓ ａｎｄ ｉｎｄｕｃｅｄ ｇｒａｐｈｓ，ａｎｄ ｇｉｖｅｓ ｔｈｅ ｐｒｉｎｃｉｐｌｅｓ ｔｏ ｊｕｄｇｅ ｔｈｅ ｉｒｒｅｄｕｃｉｂｌｅ ａｎｄ ｔｈｅ ｉｎｄｅｃｏｍｐｏｓａｂｌｅ ｏｆ ｆｉｎｉｔｅ ｇｒｏｕｐ ａｕｔｏｍａｔａ・ Ｋｅｙ ｗｏｒｄｓ：ｆｉｎｉｔｅ ｇｒｏｕｐ ａｕｔｏｍａｔａ；ｉｎｃｉｄｅｎｃｅ ｒｉｎｇ；ｉｎｄｕｃｅｄ ｇｒａｐｈ；ｉｒｒｅｄｕｃｉｂｌｅ；ｉｎｄｅｃｏｍｐｏｓａｂｌｅ （责任编辑黄 勇）
