자동세미그룹

수학에서 자동 세미그룹은 생성 세트를 나타내는 알파벳에 몇 개의 정규 언어를 갖춘 세미그룹이다.이들 언어 중 하나는 세미그룹 요소의 "캐논적 형태"를 결정하고, 다른 언어는 두 개의 표준적 형태가 발전기에 의한 곱셈에 의해 다른 요소들을 나타내는지를 결정한다.

형식적으로 $S{\displaystyle }$ ${\displaystyle S}$을(를) 세미그룹으로 $하고$ A ${\displaystyle A}$을(를) 한정된 발전기 집합으로$$ 한다.그 후 $A{\displaystyle }$ ${\displaystyle A}$에 $대한$ S$${\$displaystyle S}$의 자동 $구조$는 $A{\displaystyle }$ ${\displaystyle A}$에 대한 정규 언어 L ${\displaystyle$ L$}$로 구성되며$$, $S$ ${\displaysty S}$의 모든 요소가 $L{\displaystyle }$ ${\\\displaystyle L}$에 최소한 하나의 대표자를 두고$$ $각{\displaystyle \cup .}$${\displaystyle }${${\displaystyle \epsilon }$}$${\$displaystyle a\in$A\$cup$\{\$barepsilon$ ${\displaystyle u}$ =${\displaystyle }$v ${\displaystyle ua=v}$과$,v)$ 쌍으로 구성된 관계가 규칙적이며^#, (A^# × A)*의 하위 집합으로 간주된다.여기 A는^# 패딩 기호로 증강된 A 입니다.^[1]

자동 세미그룹 개념은 캠벨 외 연구진에 의해 자동그룹에서 일반화되었다.(2001)

자동 그룹과는 달리(Epstein et al. 1992 참조), 세미그룹은 하나의 생성 세트에 대해서는 자동 구조를 가질 수 있지만 다른 생성 세트에 대해서는 그렇지 않다.단, 자동 세미그룹에 ID가 있는 경우, 생성 집합과 관련된 자동 구조를 갖는다(Duncan et al. 1999).

의사결정 문제

자동 그룹과 마찬가지로 자동 세미그룹은 2차 시간 내에 해결할 수 있는 단어 문제를 가지고 있다.캄비테스 & 오토(2006)는 자동 모노이드의 원소가 정반대를 가지고 있는지 여부를 알 수 없다는 것을 보여주었다.

카인(2006)은 자동 세미그룹에 대해 취소율과 좌취소율 둘 다 불분명하다는 것을 증명했다.반면에, 우취소율은 자동 세미그룹(Silva & Steinberg 2004)의 경우 취소할 수 있다.

기하학적 특성화

그룹을 위한 자동 구조는 동료 여행자 특성이라고 불리는 우아한 기하학적 특성을 가지고 있다(Epstein et al. 1992, ch. 2).세미그룹을 위한 자동 구조물은 동료 여행자 특성을 가지고 있지만 일반적으로 그러한 특성이 없다(Campbell et al. 2001).그러나 특성화는 특정 '그룹 유사' 등급으로 일반화될 수 있으며, 특히 완전히 단순한 세미그룹(Campbell et al. 2002)과 그룹 임베디드 가능한 세미그룹(Cain et al. 2006)으로 일반화될 수 있다.

자동 세미그룹의 예

• 자전거 단면체
• 자유 세미그룹의 하위 세미그룹

참조

• Cain, Alan J. (2006), "Cancellativity is undecidable for automatic semigroups", Quarterly Journal of Mathematics, 57 (3): 285–295, CiteSeerX 10.1.1.106.6068, doi:10.1093/qmath/hai023
• Cain, Alan J.; Robertson, Edmund F.; Ruskuc, Nik (2006), "Subsemigroups of groups: presentations, Malcev presentations, and automatic structures", Journal of Group Theory, 9 (3): 397–426, doi:10.1515/JGT.2006.027.
• Campbell, Colin M.; Robertson, Edmund F.; Ruskuc, Nik; Thomas, Richard M. (2002), "Automatic completely simple semigroups", Acta Mathematica Hungarica, 95 (3): 201–215, doi:10.1023/A:1015632704977.
• Duncan, A. J.; Robertson, E. F.; Ruskuc, N. (1999), "Automatic monoids and change of generators", Mathematical Proceedings of the Cambridge Philosophical Society, 127 (3): 403–409, doi:10.1017/S0305004199003722.
• Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P. (1992), Word Processing in Groups, Boston, MA: Jones and Bartlett Publishers, ISBN 0-86720-244-0.
• Kambites, Mark; Otto, F (2006), "Uniform decision problems for automatic semigroups", Journal of Algebra, 303 (2): 789–809, arXiv:math/0509349, doi:10.1016/j.jalgebra.2005.11.028
• Silva, P.V.; Steinberg, B. (2004), "A geometric characterization of automatic monoids", Quarterly Journal of Mathematics, 55 (3): 333–356, CiteSeerX 10.1.1.36.1681, doi:10.1093/qmath/hah006

추가 읽기

• Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002), "Some relatives of automatic and hyperbolic groups", in Gomes, Gracinda M. S. (ed.), Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001, Singapore: World Scientific, pp. 379–406, Zbl 1031.20047