Back to Search
Start Over
LOGICAL ASPECTS OF CAYLEY-GRAPHS:: THE MONOID CASE.
- Source :
-
International Journal of Algebra & Computation . Apr2006, Vol. 16 Issue 2, p307-340. 34p. 1 Diagram, 6 Charts, 1 Graph. - Publication Year :
- 2006
-
Abstract
- Cayley-graphs of monoids are investigated under a logical point of view. It is shown that the class of monoids, for which the Cayley-graph has a decidable monadic second-order theory, is closed under free products. This result is derived from a result of Walukiewicz, stating that the decidability of monadic second-order theories is preserved under tree-like unfoldings. Concerning first-order logic, it is shown that the class of monoids, for which the Cayley-graph has a decidable first-order theory, is closed under arbitrary graph products, which generalize both, free and direct products. For the proof of this result, tree-like unfoldings are generalized to so-called factorized unfoldings. It is shown that the decidability of the first-order theory of a structure is preserved by factorized unfoldings. Several additional results concerning factorized unfoldings are shown. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181967
- Volume :
- 16
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- International Journal of Algebra & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 20594289
- Full Text :
- https://doi.org/10.1142/S0218196706003001