On the Cardinality of Sets of Infinite Trees Recognizable by Finite Automata
On the Cardinality of Sets of Infinite Trees Recognizable by Finite Automata
复制标题
DOI：
10.1007/3-540-54345-7_80
复制
发表时间：
1991-09
期刊：
影响因子：
--
通讯作者：
D. Niwinski
中科院分区：
文献类型：
--
作者：
D. Niwinski
本文证明了一个Rabin可识别树集是不可数的当且仅当它是基数连续的当且仅当它包含一个非正则树。如果Rabin可识别集L是可数的，则它可以表示为其中M是有限项的正则集，并且t1，...，普通的树。我们还设计了一个算法，给定一个Rabin自动机A，计算A所识别的树集合的基数。
We show that a Rabin recognizable set of trees is uncountable iff it is of the cardinalitycontinuumiff it contains a non-regular tree. If a Rabin recognizable setL iscountable, it can be represented aswhereMis a regular set of finite terms andt1, ...,tnare regular trees. We also design an algorithm which, given a Rabin automatonA, computes the cardinality of the set of trees recognized byA.