Some New Features and Algorithms for the Study of DFA

• 作者: Avraham N. Trahtman
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: FINITE AUTOMATON SYNCHRONIZING Word Algorithm VISUALIZATION
• 年，卷（期）: 2012,（2）
• 页码范围: 45-50
• 页数: 6页
• 分类号: O1

摘要

The work presents some new algorithms realized recently in the package TESTAS. The package decides whether or not DFA is synchronizing, several procedures find relatively short synchronizing words and a synchronizing word of the minimal length. We check whether or not a directed graph has a road coloring that turns the graph into a synchronizing deterministic finite automaton (DFA). The algorithm finds the coloring if it exists. Otherwise, the k-synchronizing road coloring can be found. We use a linear visualization of the graph of an automaton based on its structural properties.