Scholarlink

<p>This paper investigates the conditions under which a given circular (synchronizing) DFA is <i>simple</i> (sometimes referred to as <i>primitive</i>) and when it is <i>irreducible</i>. Our notion of irreducibility slightly differs from the classical one, since we are considering our monoid representations to be over <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathbb {C}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">C</mi> </math></EquationSource> </InlineEquation> instead of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\mathbb {Q}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="double-struck">Q</mi> </math></EquationSource> </InlineEquation>; nevertheless, several well-known results remain valid–for instance, the fact that every irreducible automaton is necessarily simple. We provide a complete characterization of simplicity in the circular case by means of the <i>weak contracting property</i>. Furthermore, we establish necessary and sufficient conditions for a circular <i>contracting automaton</i> (a stronger condition than the weakly contracting one) to be irreducible, and we present examples illustrating our results.</p>

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

Simplicity and irreducibility in circular automata

  • 期刊论文

  • 发表日期：

    2026年8月5日

查看全文
  • Riccardo Venturi

摘要

This paper investigates the conditions under which a given circular (synchronizing) DFA is simple (sometimes referred to as primitive) and when it is irreducible. Our notion of irreducibility slightly differs from the classical one, since we are considering our monoid representations to be over \(\mathbb {C}\) C instead of \(\mathbb {Q}\) Q ; nevertheless, several well-known results remain valid–for instance, the fact that every irreducible automaton is necessarily simple. We provide a complete characterization of simplicity in the circular case by means of the weak contracting property. Furthermore, we establish necessary and sufficient conditions for a circular contracting automaton (a stronger condition than the weakly contracting one) to be irreducible, and we present examples illustrating our results.