Fixed points vs. infinite generation
Fixed points vs. infinite generation
复制标题
固定点与无限生成
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
D. Niwinski
中科院分区：
文献类型：
--
作者：
D. Niwinski
作者基于树的标准幂集代数的基本运算，刻画了无限树不动点定义的性质的Rabin可定义性（见M.O. Rabin, 1969），涉及最小和最大不动点算子以及有限并算子和函数组合。建立了由最小和最大不动算子交替产生的层次与自动机的拉宾指数引起的层次之间的严格联系。表征结果实际上是在更一般的层面上证明的，即对于任意幂集代数，其中Rabin自动机的概念被更一般的无限语法概念所取代。<<ETX>>
The author characterizes Rabin definability (see M.O. Rabin, 1969) of properties of infinite trees of fixed-point definitions based on the basic operations of a standard powerset algebra of trees and involving the least and greatest fixed-point operators as well as the finite union operator and functional composition. A strict connection is established between a hierarchy resulting from alternating the least and greatest fixed-point operators and the hierarchy induced by Rabin indices of automata. The characterization result is actually proved on a more general level, namely, for arbitrary powerset algebra, where the concept of Rabin automaton is replaced by the more general concept of infinite grammar.<<ETX>>