가중 오토마톤

이론 컴퓨터 과학과 형식 언어 이론에서, 가중치 자동 기계 또는 가중치 유한 상태 기계는 에지가 예를 들어 실수나 정수 같은 가중치를 갖는 유한 상태 기계의 일반화이다.유한 상태 머신은 결정 문제에 대한 답변만 할 수 있습니다.이러한 머신은 문자열을 입력으로 받아들여 부울 출력(예: "승인" 또는 "거부")을 생성합니다.이와는 대조적으로 가중치 오토마타는 정량적 출력, 예를 들어 주어진 입력 문자열에 대해 몇 개의 응답이 가능한지 또는 확률 ^[1]분포에 따른 입력 문자열의 개연성을 생성한다.그것들은 정량적 오토마타의 ^[2]^{: Fig.1}가장 단순한 연구 모델 중 하나이다.

가중치 오토마톤의 정의는 일반적으로 임의의 $세미링$ R $({displaystyle$ R $R$ 덧셈 $+$ 연산 $\times$ +({ $displaystyle$ $\times$ +}) 및 곱셈 $\times$ 연산 ×({ $displaystyle$ \times $\times$ 에 $+$ 대해 주어진다. 오토마톤은 유한한 상태 집합, 유한한 문자 입력 알파벳으로 $\Sigma$ 되어 $있다$ $isplaystyle \Sigma }$ 및 $\Sigma$ 엣지( $\displaystyle \Sigma)$ 의 $\Sigma$ 문자 및 R $(\displaystyle$ R $R$ 의 중량으로 라벨이 붙여진 모든 경로의 중량으로 정의됩니다.자동화 내의 모든 경로의 가중치는 스트린으로 라벨이 붙여진 모든 경로의 가중치의 합계입니다.g. 가중치 오토마톤은 $\Sigma ^{*}$ ${\$ display(\ $displaystyle \Sigma$ ^{*})에서 $\Sigma ^{*}$ R $(\displaystyle$ R $R$ ^[1]까지의 함수를 정의합니다.

가중치 오토마타는 결정론적 유한 오토마타(DFA)와 비결정론적 유한 오토마타(NFA)를 일반화하며, 여기서 덧셈은 논리적 분리, 곱셈은 논리적 결합이다.DFA의 경우 입력 문자열에 대한 허용 경로는 1개뿐이므로 분리가 적용되지 않습니다.가중치가 실수이고 각 상태에 대한 발신 가중치가 1에 더해지는 경우, 가중치 오토마타는 확률론적 모델로 간주될 수 있으며 확률론적 오토마타라고도 한다.이러한 기계는 모든 문자열에 대한 확률 분포를 정의하며 마르코프 의사결정 과정 및 마르코프 연쇄와 같은 다른 확률론적 모델과 관련이 있습니다.

가중치 오토마타는 자연어 처리에서 사용되며, ^[3]^[1]^{: 571–596}단어와 문장에 가중치를 할당하고 이미지 ^[1]^{: 453–480}압축에도 사용됩니다.그것들은 Marcel-Paul Schützenberger에 의해 1961년 ^[4]오토마타 패밀리의 정의에 관한 논문에서 처음 소개되었습니다.도입 이후, 중첩 가중치^[5] 오토마타와 가중치 유한 상태 ^[6]변환기와 같은 많은 확장이 제안되었다.연구자들은 입력-출력 동작^[7](컴퓨터 학습 이론 참조)에서 기계를 학습하고 결정 가능성 ^[8]질문을 연구하는 관점에서 가중치 오토마타를 연구했다.

정의.

가환세미링(또는 리그)은 2개의 $0\neq 1$ 0 $0\neq 1$ 1({ $displaystyle$ 0 $\neq$ 1)과 $0\neq 1$ 덧셈 및 $\otimes$ 곱셈 연산 $({displaystyle \oplus})$ 을 $\otimes$ 갖춘 집합 R로, $\oplus$ $\otimes$ $displaystyle$ \ $oplus}$ 가 $\oplus$ $\oplus$ 가환되고 $identity$ 0({ $displaystyle$ $\$ oplus})과 관련지어집니다. $0$ $"{displaystyle \otimes}"$ 는 $\otimes$ $ID$ 1(\ $displaystyle$ 1) $\oplus$ 및 $\otimes$ "{ $displaystyle$ \ $oplus$ 배포와 $\otimes$ 교환 및 관련지어지며, "0"은 $"\displaystyle \otimes$ 의 흡수 요소입니다.

$R에$ $대한$ 가중 $오토마톤$ 은 ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ A ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ ( ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ , ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ , ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ , ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ , ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ ) { $displaystyle$ { ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ A } = ( $Q$ , \ $Sigma ,$ \ $Delta , I$ , F $}$ 입니다 ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ .

$(\displaystyle$ Q $)$ 는 $Q$ 유한한 상태의 집합입니다.
$σ$ \ $displaystyle$ \ $\Sigma$ Sigma $\Sigma$ }는 유한 알파벳입니다.
$\Delta \subseteq Q\times \Sigma \times R\times Q$ × $\Delta \subseteq Q\times \Sigma \times R\times Q$ $\Delta \subseteq Q\times \Sigma \times R\times Q$ × Q ( \ $displaystyle$ \ $Delta$ \ $subseteq \$ times \ $Sigma$ \ times $R$ \ $\Delta \subseteq Q\times \Sigma \times R\times Q$ times Q )는 유한한 $(q,\sigma ,w,q')$ 세트입니다( $(q,\sigma ,w,q')$ , $(q,\sigma ,w,q')$ \ $displaystyle$ ( $q$ , \ $sigma$ , w $(q,\sigma ,w,q')$ , $(q,\sigma ,w,q')$ q ) ） $(q,\sigma ,w,q')$ $。여기$ 서 \ $displaystyle$ w , , , $and$ is and and and and and and and and and and and and and and and ands and and and and and andssss $\sigma$ and and 。
$I:Q\to R$ $Q\to$ R은 $I:Q\to R$ 초기 무게 함수입니다.
$F:Q\to R$ $Q\to$ R은 $F:Q\to R$ 최종 무게 함수입니다.

$w\in \Sigma ^{*}$ w의 경로 $displaystyle$ w $\in \Sigma$ ^{*})는 $w\in \Sigma ^{*}$ 그래프 내의 유한 경로입니다.문자 라벨의 결합은 w $\displaystyle$ w $w$ 와 $같습니다$ . $q_{0},q_{1},\ldots ,q_{n}$ $q_{0},q_{1},\ldots ,q_{n}$ 0 $q_{0},q_{1},\ldots ,q_{n}$ $q_{0},q_{1},\ldots ,q_{n}$ 1 $q_{0},q_{1},\ldots ,q_{n}$ n { $displaystyle q$ _ { $0$ , $q _ { n$ $I(q_{0})\otimes I(q_{n})$ } $\otimes$ is is $q_{0},q_{1},\ldots ,q_{n}$ the the the the the the the the the the the ( ( ( ( ( ( ( ( ( ( ( ( the the the the the the $I(q_{0})\otimes I(q_{n})$ \ $displaystyle$ $q$ _ $0$ $I(q_{0})\otimes I(q_{n})$ $\otimes$ ( $I(q_{0})\otimes I(q_{n})$ ( $\otimes$ $n0$ )를 곱한 값입니다.w $\displaystyle$ w라는 $w$ $w$ 의 무게는 $입력$ w $\displaystyle$ $\oplus$ w $\$ $oplus$ 또는 허용 경로가 없는 경우 0 $)$ 의 모든 경로 가중치 합계입니다.이러한 방식으로 기계는 $[\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R$ [ $[\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R$ : $[\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R$ $[\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R$ {\ $displaystyle [\!$ $[{\mathcal {A}}}\]:$ $\Sigma ^{*}\to$ R $[\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R$

A $(\$ 의 ${\mathcal {A}}$ 기본 NFA는 $0$ 가0(\ $displaystyle$ 0 $\Delta$ 인 $0$ 모든 트랜지션을 삭제한 다음 $\Delta$ 의 모든 웨이트를 지우고 새로운 트랜지션이 $Q\times \Sigma \times Q$ Q × $Q\times \Sigma \times Q$ D × $Q\times \Sigma \times Q$ \ $times \Times$ 로 $Q\times \Sigma \times Q$ 된 NFA입니다.l상태와 final상태는 $I(q)\neq 0$ 각각 I $I(q)\neq 0$ 0 $I(q)\neq 0$ \ $displaystyle$ I $(q)$ \ $neq$ 0 $I(q)\neq 0$ $F(q)\neq 0$ F ( $F(q)\neq 0$ q )≠ $F(q)\neq 0$ 0 \ $displaystyle F$ (q) \ $neq$ 0 $F(q)\neq 0$ {\ {\ q q0 0 \ $displaystyle$ F(q $q$ ) \ neq 0 $I(q)\neq 0$ q q q of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of

바리에이션

가중 자동화는 기본 NFA가 결정론적인 경우 결정론적이고 기본 NFA가 모호하지 않은 경우 모호하지 않다.이 경우 항상 1개의 허용 경로가 존재하기 때문에 $"\displaystyle\oplus"$ 연산은 $\oplus$ 적용되지 않으며 정의에서 생략할 수 있습니다.

정의를 확장하여 엡실론 트랜지션 $(q,\epsilon ,w,q')$ $(q,\epsilon ,w,q')$ , $(q,\epsilon ,w,q')$ " ) ${display (q,\epsilon, w, q$ ' $(q,\epsilon ,w,q')$ )을 허용할 수 있습니다. $여기서$ "\displaystyle \ $epsilon }$ 은 $\epsilon$ 빈 문자열입니다.이 경우 엡실론 천이 사이클이 없어야 합니다.이것은 가중치 오토마타의 ^[1]^[9]표현력을 증가시키지 않습니다.엡실론 전환이 허용되는 경우, 초기 가중치와 최종 가중치는 표현력의 손실 없이 초기 및 최종 상태 세트로 대체될 수 있다.

트랜지션 함수는 $\sigma$ 의 트랜지션이 아닌 $매트릭스$ $\Delta _{\sigma }\in R^{Q\times Q}$ $\Delta _{\sigma }\in R^{Q\times Q}$ Q × $\Delta _{\sigma }\in R^{Q\times Q}$ (\ $displaystyle$ $\Delta$ _ ${\sigma$ $\sigma$ $in$ R $^{$ $Q$ $\times$ Q})로 $\Delta _{\sigma }\in R^{Q\times Q}$ $지정$ 할 수 있습니다 $.$ $(q,q')$ , q $(q,q')$ " ) $(q,q')$ { $displaystyle ( q$ , $(q,q')$ q ) } 에서의 $(q,q')$ 매트릭스 엔트리는 ( $(q,\sigma ,q')$ , $(q,\sigma ,q')$ " , $(q,\sigma ,q')$ " ) { $displaystyle ( q$ , \ $sigma , q$ ) $(q,\sigma ,q')$ } $(q,\sigma ,q')$ ^[1]^[10]에서의 모든 트랜지션의 합계입니다.

일부 필자는 초기 및 최종 무게 $함수$ I $($ $디스플레이$ $스타일$ I $)$ 및 $I$ F $(디스플레이 스타일$ F $F$ ^[2]를 생략하고 대신I( $디스플레이$ 스타일 $I$ I $)$ $및$ F( $디스플레이$ 스타일 F $)$ 는 $F$ $초기$ 및 최종 상태로 대체됩니다.엡실론 전환이 존재하지 않는 경우 $[\![{\mathcal {A}}]\!](\varepsilon )$ [ ${\)\displaystyle [\!$ $[{\mathcal {A}}\!"(\varepsilon)}:$ 초기 $[\![{\mathcal {A}}]\!](\varepsilon )$ 상태와 최종 상태의 수에만 의존합니다.

일부 저자는 특히 결정 가능성 ^[2]^[8]^[4]결과를 연구할 때 N $\mathbb {N}$ \ $mathbb$ {N $}$ $\mathbb {Z}$ Z {\ $displaystyle \mathbb {Z$ 와 $\mathbb {N}$ 특정 세미링으로 제한한다.

$"\displaystyle\oplus"$ 에 $\oplus$ 0 요소가 있는 요건이 생략되는 경우가 있습니다.이 경우 기계는 전체 함수가 아닌 $\$ 부터 $\Sigma ^{*}$ $\displaystyle$ R까지의 $R$ 부분 함수를 정의합니다.

「」를 참조해 주세요.

확률적 자동화

비결정론적 유한 오토마톤

유한 상태 변환기

유리 급수

세미링

매트릭스 링

타임오토마톤

퍼지 논리

마르코프 연쇄

레퍼런스

^ ^a ^b ^c ^d ^e ^f Droste, Manfred; Kuich, Werner; Vogler, Heiko, eds. (2009). "Handbook of Weighted Automata". Monographs in Theoretical Computer Science. doi:10.1007/978-3-642-01492-5. ISSN 1431-2654. chs.1-4, 페이지 3-26, 69-71, 122-1992.
^ ^a ^b ^c Chatterjee, Krishnendu; Henzinger, Thomas A.; Otop, Jan (2016). Rival, Xavier (ed.). "Quantitative Monitor Automata". Static Analysis. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 23–38. doi:10.1007/978-3-662-53413-7_2. ISBN 978-3-662-53413-7.
^ Chiang, David. "Weighted Automata" (PDF). Natural Language Processing (CSE 40657/60657), course notes, Fall 2019. Retrieved 2021-11-09.{{cite web}}: CS1 maint :url-status (링크)
^ ^a ^b Schützenberger, M. P. (1961-09-01). "On the definition of a family of automata". Information and Control. 4 (2): 245–270. doi:10.1016/S0019-9958(61)80020-X. ISSN 0019-9958.
^ Chatterjee, Krishnendu; Henzinger, Thomas A.; Otop, Jan (2017-12-14). "Nested Weighted Automata". ACM Transactions on Computational Logic. 18 (4): 31:1–31:44. doi:10.1145/3152769. ISSN 1529-3785.
^ Mohri, Mehryar; Pereira, Fernando; Riley, Michael (2002-01-01). "Weighted finite-state transducers in speech recognition". Computer Speech & Language. 16 (1): 69–88. doi:10.1006/csla.2001.0184. ISSN 0885-2308.
^ Balle, Borja; Mohri, Mehryar (2015). Maletti, Andreas (ed.). "Learning Weighted Automata". Algebraic Informatics. Lecture Notes in Computer Science. Cham: Springer International Publishing: 1–21. doi:10.1007/978-3-319-23021-4_1. ISBN 978-3-319-23021-4.
^ ^a ^b Almagor, Shaull; Boker, Udi; Kupferman, Orna (2011). Bultan, Tevfik; Hsiung, Pao-Ann (eds.). "What's Decidable about Weighted Automata?". Automated Technology for Verification and Analysis. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 482–491. doi:10.1007/978-3-642-24372-1_37. ISBN 978-3-642-24372-1.
^ Mohri, Mehryar (2009), Droste, Manfred; Kuich, Werner; Vogler, Heiko (eds.), "Weighted Automata Algorithms", Handbook of Weighted Automata, Monographs in Theoretical Computer Science. An EATCS Series, Berlin, Heidelberg: Springer, pp. 213–254, doi:10.1007/978-3-642-01492-5_6, ISBN 978-3-642-01492-5, retrieved 2021-11-11
^ Droste, Manfred; Gastin, Paul (2007-06-21). "Weighted automata and weighted logics". Theoretical Computer Science. Automata, Languages and Programming. 380 (1): 69–86. doi:10.1016/j.tcs.2007.02.055. ISSN 0304-3975.

[Handbook-1] ^ ^a ^b ^c ^d ^e ^f Droste, Manfred; Kuich, Werner; Vogler, Heiko, eds. (2009). "Handbook of Weighted Automata". Monographs in Theoretical Computer Science. doi:10.1007/978-3-642-01492-5. ISSN 1431-2654. chs.1-4, 페이지 3-26, 69-71, 122-1992.

[QuantitativeAutomata-2] Chatterjee, Krishnendu; Henzinger, Thomas A.; Otop, Jan (2016). Rival, Xavier (ed.). "Quantitative Monitor Automata". Static Analysis. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 23–38. doi:10.1007/978-3-662-53413-7_2. ISBN 978-3-662-53413-7.

[3] Chiang, David. "Weighted Automata" (PDF). Natural Language Processing (CSE 40657/60657), course notes, Fall 2019. Retrieved 2021-11-09.{{cite web}}: CS1 maint :url-status (링크)

[Introduced-4] Schützenberger, M. P. (1961-09-01). "On the definition of a family of automata". Information and Control. 4 (2): 245–270. doi:10.1016/S0019-9958(61)80020-X. ISSN 0019-9958.

[5] Chatterjee, Krishnendu; Henzinger, Thomas A.; Otop, Jan (2017-12-14). "Nested Weighted Automata". ACM Transactions on Computational Logic. 18 (4): 31:1–31:44. doi:10.1145/3152769. ISSN 1529-3785.

[6] Mohri, Mehryar; Pereira, Fernando; Riley, Michael (2002-01-01). "Weighted finite-state transducers in speech recognition". Computer Speech & Language. 16 (1): 69–88. doi:10.1006/csla.2001.0184. ISSN 0885-2308.

[7] Balle, Borja; Mohri, Mehryar (2015). Maletti, Andreas (ed.). "Learning Weighted Automata". Algebraic Informatics. Lecture Notes in Computer Science. Cham: Springer International Publishing: 1–21. doi:10.1007/978-3-319-23021-4_1. ISBN 978-3-319-23021-4.

[Decidability-8] Almagor, Shaull; Boker, Udi; Kupferman, Orna (2011). Bultan, Tevfik; Hsiung, Pao-Ann (eds.). "What's Decidable about Weighted Automata?". Automated Technology for Verification and Analysis. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 482–491. doi:10.1007/978-3-642-24372-1_37. ISBN 978-3-642-24372-1.

[9] Mohri, Mehryar (2009), Droste, Manfred; Kuich, Werner; Vogler, Heiko (eds.), "Weighted Automata Algorithms", Handbook of Weighted Automata, Monographs in Theoretical Computer Science. An EATCS Series, Berlin, Heidelberg: Springer, pp. 213–254, doi:10.1007/978-3-642-01492-5_6, ISBN 978-3-642-01492-5, retrieved 2021-11-11

[10] Droste, Manfred; Gastin, Paul (2007-06-21). "Weighted automata and weighted logics". Theoretical Computer Science. Automata, Languages and Programming. 380 (1): 69–86. doi:10.1016/j.tcs.2007.02.055. ISSN 0304-3975.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search

가중 오토마톤

네임스페이스

더

목차

정의.

바리에이션

「」를 참조해 주세요.

레퍼런스

Search

가중 오토마톤

정의.

바리에이션

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.