Semigrupo automático
En matemáticas , un semigrupo automático es un semigrupo generado finitamente equipado con varios idiomas regulares sobre un alfabeto que representa un grupo electrógeno. Uno de estos lenguajes determina "formas canónicas" para los elementos del semigrupo, los otros lenguajes determinan si dos formas canónicas representan elementos que se diferencian por la multiplicación de un generador.
Formalmente, sea un semigrupo y sea un conjunto finito de generadores. Entonces, una estructura automática para con respecto a consiste en un lenguaje regular sobre tal que cada elemento de tiene al menos un representante en y tal que para cada uno , la relación que consiste en pares con es regular, visto como un subconjunto de ( A # × A # ) *. Aquí A # es A aumentado con un símbolo de relleno. [1]
El concepto de un semigrupo automático fue generalizado a partir de grupos automáticos por Campbell et al. (2001)
A diferencia de los grupos automáticos (ver Epstein et al. 1992), un semigrupo puede tener una estructura automática con respecto a un grupo electrógeno, pero no con respecto a otro. Sin embargo, si un semigrupo automático tiene una identidad, entonces tiene una estructura automática con respecto a cualquier grupo electrógeno (Duncan et al. 1999).
Al igual que los grupos automáticos, los semigrupos automáticos tienen problemas de palabras que se pueden resolver en tiempo cuadrático. Kambites y Otto (2006) demostraron que es indecidible si un elemento de un monoide automático posee una inversa derecha.
Cain (2006) demostró que tanto la cancelatividad como la cancelatividad a la izquierda son indecidibles para los semigrupos automáticos. Por otro lado, la cancelatividad a la derecha es decidible para semigrupos automáticos (Silva y Steinberg 2004).