<p>We are concerned with the <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation>-reducibility of&#xa0;pseudovarieties of&#xa0;ordered monoids representing half levels of&#xa0;concatenation hierarchies. In the author’s paper (Int. J. Algebra Comput. <b>64</b>(01), 87–135, 2024), the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation>-reducibility of&#xa0;pseudovarieties representing levels 1/2 and 3/2 of&#xa0;concatenation hierarchies with a&#xa0;locally finite basic pseudovariety has been proven, using results of&#xa0;the paper by Place (Log. Methods Comput. Sci. <b>14</b>(4:16), 1–58, 2018) on so called covering of&#xa0;corresponding sets of&#xa0;regular languages. In this paper, we prove the same results on the <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation>-reducibility, not using the results of&#xa0;the mentioned paper by&#xa0;Place, although still inspired by their proofs. This new method of&#xa0;the proofs of&#xa0;the <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\omega \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation>-reducibility prepares us to their potential extension to higher half levels of&#xa0;concatenation hierarchies. The process of&#xa0;a&#xa0;gradual generalization is initiated in this paper.</p>

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

A purely algebraic proof of the omega-reducibility of pseudovarieties representing low half levels of concatenation hierarchies

  • Jana Volaříková

摘要

We are concerned with the \(\omega \) ω -reducibility of pseudovarieties of ordered monoids representing half levels of concatenation hierarchies. In the author’s paper (Int. J. Algebra Comput. 64(01), 87–135, 2024), the \(\omega \) ω -reducibility of pseudovarieties representing levels 1/2 and 3/2 of concatenation hierarchies with a locally finite basic pseudovariety has been proven, using results of the paper by Place (Log. Methods Comput. Sci. 14(4:16), 1–58, 2018) on so called covering of corresponding sets of regular languages. In this paper, we prove the same results on the \(\omega \) ω -reducibility, not using the results of the mentioned paper by Place, although still inspired by their proofs. This new method of the proofs of the \(\omega \) ω -reducibility prepares us to their potential extension to higher half levels of concatenation hierarchies. The process of a gradual generalization is initiated in this paper.