首页    期刊浏览 2024年11月29日 星期五
登录注册

文章基本信息

  • 标题:Generation of Constants and Synchronization of Finite Automata
  • 作者:Arto Salomaa
  • 期刊名称:Journal of Universal Computer Science
  • 印刷版ISSN:0948-6968
  • 出版年度:2002
  • 卷号:8
  • 期号:2
  • 页码:332-347
  • 出版社:Graz University of Technology and Know-Center
  • 摘要:

    The problem about the synchronization of a finite deterministic automaton is not yet properly understood. The present paper investigates this and related problems within the general framework of a composition theory for functions over a finite domain N with n elements. The notion of depth introduced in this connection is a good indication of the complexity of a given function, namely, the complexity with respect to the length of composition sequences in terms of functions belonging to a basic set. The depth may vary considerably with the target function. Not much is known about the reachability of some target functions, notably constants. Synchronizability of a finite automaton amounts to the representability of some constant as a composition of the functions defined by the input letters. Properties of n such as primality or being a power of 2 turn out to be important, independently of the semantic interpretation. We present some necessary, as well as some sufficient, conditions for synchronizability. We also discuss a famous conjecture about the length of the shortest synchronizing word, and present some results about universal synchronizing words.

    1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen.
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有