Uniformization in Automata Theory

Uniformization in Automata Theory
复制标题

自动机理论中的均匀化

DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Christof L¨oding
Christof L¨oding
中科院分区：
--
文献类型：
--
作者：
Arnaud Carayol;Christof L¨oding

文献摘要

被引文献

相似文献

本文综述了自动机可定义函数对自动机可定义关系的一致化的一些经典结果。我们考虑有限和无限词和树上的自动关系以及有限和无限词上的理性关系的情况。我们还提供了一些新的结果，关于统一的自动和理性的关系，有限的话，由连续换能器。我们表明，它是不可判定的一个给定的合理的关系是否可以统一的连续换能器，并提供了一个自动关系的情况下的决策程序。
We survey some classical results on uniformizations of automaton de-finable relations by automaton definable functions. We consider the case of automatic relations over finite and infinite words and trees as well as rational relations over finite and infinite words. We also provide some new results concerning the uniformization of automatic and rational relations over finite words by subsequential transducers. We show that it is undecidable whether a given rational relation can be uniformized by a subsequential transducer and provide a decision procedure for the case of automatic relations.