The Join Levels of the Trotter-Weil Hierarchy Are Decidable

DOI10.1007/978-3-642-32589-2_53zbMATH Open1365.68335arXiv1204.4672OpenAlexW1728819265MaRDI QIDQ2912759FDOQ2912759

Authors: Manfred Kufleitner, Alexander Lauser 

Publication date: 25 September 2012

Published in: Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Abstract: The variety DA of finite monoids has a huge number of different characterizations, ranging from two-variable first-order logic FO^2 to unambiguous polynomials. In order to study the structure of the subvarieties of DA, Trotter and Weil considered the intersection of varieties of finite monoids with bands, i.e., with idempotent monoids. The varieties of idempotent monoids are very well understood and fully classified. Trotter and Weil showed that for every band variety V there exists a unique maximal variety W inside DA such that the intersection with bands yields the given band variety V. These maximal varieties W define the Trotter-Weil hierarchy. This hierarchy is infinite and it exhausts DA; induced by band varieties, it naturally has a zigzag shape. In their paper, Trotter and Weil have shown that the corners and the intersection levels of this hierarchy are decidable. In this paper, we give a single identity of omega-terms for every join level of the Trotter-Weil hierarchy; this yields decidability. Moreover, we show that the join levels and the subsequent intersection levels do not coincide. Almeida and Azevedo have shown that the join of R-trivial and L-trivial finite monoids is decidable; this is the first non-trivial join level of the Trotter-Weil hierarchy. We extend this result to the other join levels of the Trotter-Weil hierarchy. At the end of the paper, we give two applications. First, we show that the hierarchy of deterministic and codeterministic products is decidable. And second, we show that the direction alternation depth of unambiguous interval logic is decidable.

Full work available at URL: https://arxiv.org/abs/1204.4672

Recommendations

• A join theorem for the computably enumerable degrees
• Hadwiger's conjecture is decidable
• Decomposability of low 2-computably enumerable degrees and Turing jumps in the Ershov hierarchy
• Towards Decidability of Conjugacy of Pairs and Triples
• On decidability of intermediate levels of concatenation hierarchies
• Turing degrees in refinements of the arithmetical hierarchy
• Finitely Decidable Congruence Modular Varieties
• Decidability and computability of certain torsion-free abelian groups
• 𝐾-trivial degrees and the jump-traceability hierarchy
• A Characterization of Finitely Decidable Congruence Modular Varieties

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Varieties and pseudovarieties of semigroups (20M07)

Cited In (7)

• One quantifier alternation in first-order logic with modular predicates
• The word problem for omega-terms over the Trotter-Weil hierarchy
• The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• The amazing mixed polynomial closure and its applications to two-variable first-order logic
• Conelikes and ranker comparisons
• How many times do you need to go back to the future in unary temporal logic?

This page was built for publication: The Join Levels of the Trotter-Weil Hierarchy Are Decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912759)