Stretching and jamming of automata
Stretching and jamming of automata
复制标题
自动机的拉伸和干扰
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
D. Kourie
中科院分区：
文献类型：
--
作者：
Noud de Beijer;B. Watson;D. Kourie
本文给出了自动机上的两种变换，即拉伸变换和干扰变换。在某些条件下，这些转换将减少转换表的大小，而在其他条件下，将减少字符串识别时间。给定一个确定性有限自动机，我们可以通过将每个单一转换转换为两个或多个顺序转换来扩展它，从而引入额外的中间状态。干扰是相反的转换，将两个或多个连续的转换转换为单个转换，从而消除冗余的中间状态。我们将给出拉伸和干扰的正式定义。我们将给出拉伸和干扰的算法，并计算拉伸/干扰在内存消耗和字符串识别时间方面有效的理论界限。
In this paper we present two transformations on automata, called stretching and jamming. These transformations will, under certain conditions, reduce the size of the transition table, and under other conditions reduce the string recognition time. Given a deterministic finite automaton, we can stretch it by transforming each single transition into two or more sequential transitions, thereby introducing additional intermediate states. Jamming is the opposite transformation, in which two or more successive transitions are transformed into a single transition, thereby removing redundant intermediate states.We will present formal definitions of stretching and jamming. We will give algorithms for stretching and jamming and we will calculate theoretical bounds, when stretching/jamming is effective in terms of memory consumption and string recognition time.
系统性能建模
DOI：
--
发表时间：
2021
期刊：
影响因子：
--
作者：
三坂孝志 ; 久保世志 ; 淺海典男 ; 出田武臣 ; 大林茂;Y. Tamura and S. Yamada
通讯作者：
Y. Tamura and S. Yamada