The present paper introduces centralized versions of jumping finite automata and gives the principal reason for their introduction in terms of today’s discontinuous computation in practice. In essence, a centralized version, C, works just like the original uncentralized version of these automata except that C contains a special central symbol, #, whose single occurrence is always inserted into an input word, w. C performs a jump in such a way that it replaces a subword containing # with  one #. If, by making a sequence of jumps in this centralized way, it eventually wipes out all w with # as the only symbol unerased, C accepts w; the set of all accepted words in this way is the language of C. This paper shows that the language family resulting from these centralized versions coincides with that of linear languages. In addition, this paper defines several special cases of these centralized versions and demonstrates their equivalences to special cases of linear grammars, such as minimal and even linear grammars. Consequently, in terms of the language theory, all the variety of centralized jumping finite automata can be seen as automaton-based counterparts to linear grammars and their special cases.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Centralized Versions of Jumping Finite Automata

  • Alexander Meduna,
  • Zdeněk Foltýn

摘要

The present paper introduces centralized versions of jumping finite automata and gives the principal reason for their introduction in terms of today’s discontinuous computation in practice. In essence, a centralized version, C, works just like the original uncentralized version of these automata except that C contains a special central symbol, #, whose single occurrence is always inserted into an input word, w. C performs a jump in such a way that it replaces a subword containing # with  one #. If, by making a sequence of jumps in this centralized way, it eventually wipes out all w with # as the only symbol unerased, C accepts w; the set of all accepted words in this way is the language of C. This paper shows that the language family resulting from these centralized versions coincides with that of linear languages. In addition, this paper defines several special cases of these centralized versions and demonstrates their equivalences to special cases of linear grammars, such as minimal and even linear grammars. Consequently, in terms of the language theory, all the variety of centralized jumping finite automata can be seen as automaton-based counterparts to linear grammars and their special cases.