8 votos

Decidibilidad del problema de membresía para el grupo Baitarlag Solitar$BS(1,2)$

Es el subsemigroup o subgrupo de pertenencia problema para $BS(1,2)$ decidable ?

Esto es, dados los elementos de $g,g_1,g_2,\dots,g_n$ de $BS(1,2)$, existe un procedimiento de decisión para comprobar si $g$ pertenece a la semigroup/subgrupo generado por a$\{g_1,g_2,\dots,g_n\}$?

Tenga en cuenta que el decidability de la semigroup de afiliación implica la decidability de subgrupo membresía problema y la undecidability del subgrupo de pertenencia problema implica la undecidability de la semigroup membresía problema.

7voto

Shinwari Puntos 11

Hay dos preguntas aquí, el "grupo" de la pregunta y de la "semigroup" pregunta. La respuesta es "sí" al grupo la pregunta y "no sé" a la semigroup pregunta.

El grupo en cuestión se refiere a menudo como la generalizada palabra problema (y archaically como la aparición del problema). Un grupo es metabelian si su derivada subgrupo es abelian. El grupo $BS(1, 2)$ (y, más generalmente, $BS(1, n)$) es un metabelian grupo. Romanovskii demostrado que la generalización de la palabra problema es soluble para metabelian grupos (la referencia es: Romanovskii, N. S. Algunos algorítmica de problemas para la solución de los grupos. Álgebra i Logika, (1974) 13(1):26-34.). Por lo tanto, la respuesta del "grupo" la pregunta es "sí".

Para el semigroup pregunta, no sé la respuesta. En particular, simplemente no se puede usar "metabelian" como hicimos para el grupo de que se trate. Esto es debido a que el libre metabelian grupo de rango dos ha indecidible subsemigroup membresía problema (la referencia es: Lohrey, M. & Steinberg, B. y Embaldosados Submonoids de Metabelian Grupos. La Teoría De La Comput. Syst. (2011) 48: 411-427. doi).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X