论文标题
非确定自动机和JSL-DFA
Nondeterministic Automata and JSL-dfas
论文作者
论文摘要
我们介绍了依赖关系自动机的类别。依赖性自动机由两个非确定有限自动机组成，其状态之间的关系满足条件。此类别等于在Join-Semilattices（即JSL-DFAS）中解释的确定性有限自动机。规范依赖性自动机接受$ l $的金额为$ l $ $ l $和$ rev（l）$的州最小DFA，由“依赖关系”连接。 我们将许多规范的JSL-DFA描述为依赖性自动机，并解释/扩展Brzozowski的算法。如果其各个状态在左/右手和设定理论布尔操作下接受$ \ {l \} $的关闭中的语言，请致电NFA“亚原子”。我们证明NFA $ n $是亚原子IFF $ RSC（REV（n））$的过渡单体是句法。
We introduce the category of dependency automata. A dependency automaton consists of two nondeterministic finite automata, with a relation between their states satisfying conditions. This category is equivalent to deterministic finite automata interpreted in join-semilattices i.e. JSL-dfas. The canonical dependency automaton accepting $L$ amounts to the state-minimal dfas for $L$ and $rev(L)$ connected by the `dependency relation'. We describe many canonical JSL-dfas as dependency automata and also explain/extend Brzozowski's algorithm. Call an nfa `subatomic' if its individual states accept a language in the closure of $\{L\}$ under left/right quotients and set-theoretic boolean operations. We prove an nfa $N$ is subatomic iff $rsc(rev(N))$'s transition monoid is syntactic.
