Взвешенный автомат

В теоретической информатике и теории формального языка или взвешенный автомат взвешенный конечный автомат — это обобщение конечного автомата , в котором ребра имеют веса , например действительные числа или целые числа . Конечные автоматы способны решать только задачи принятия решений ; они принимают в качестве входных данных строку и выдают логический результат, т.е. либо «принять», либо «отклонить». Напротив, взвешенные автоматы выдают количественный результат, например, подсчитывают, сколько ответов возможно для данной входной строки, или вероятность того, насколько вероятна входная строка в соответствии с распределением вероятностей . ^[2] Они являются одной из простейших изученных моделей количественных автоматов. ^[1]^{: Рисунок 1}

Определение взвешенного автомата обычно дается над произвольным полукольцом. $R$ , абстрактный набор с операцией сложения $+$ и операция умножения $\times$ . Автомат состоит из конечного набора состояний, конечного входного алфавита символов $\Sigma$ и края, которые помечены как символом в $\Sigma$ и вес в $R$ . Вес любого пути в автомате определяется как произведение весов вдоль пути, а вес строки — это сумма весов всех путей, помеченных этой строкой. Таким образом, взвешенный автомат определяет функцию из $\Sigma ^{*}$ к $R$ . ^[2]

Взвешенные автоматы обобщают детерминированные конечные автоматы (DFA) и недетерминированные конечные автоматы (NFA), которые соответствуют взвешенным автоматам над булевым полукольцом , где сложение является логической дизъюнкцией , а умножение - логической конъюнкцией . В случае DFA для любой входной строки существует только один принимающий путь, поэтому дизъюнкция не применяется. Когда веса являются действительными числами, а исходящие веса для каждого состояния добавляются к единице, взвешенные автоматы можно рассматривать как вероятностную модель и также известны как вероятностные автоматы . Эти машины определяют распределение вероятностей по всем строкам и связаны с другими вероятностными моделями, такими как процессы принятия решений Маркова и цепи Маркова .

Взвешенные автоматы находят применение в обработке естественного языка , где они используются для присвоения весов словам и предложениям. ^[3]^[2]^{: 571–596} а также в сжатии изображений . ^[2]^{: 453–480} Впервые они были представлены Марселем-Полем Шютценбергером в его статье 1961 года « Об определении семейства автоматов». ^[4] С момента их появления было предложено множество расширений, например вложенные взвешенные автоматы, ^[5] автоматы учета затрат, ^[6] и взвешенные преобразователи с конечным состоянием . ^[7] Исследователи изучили взвешенные автоматы с точки зрения изучения машины по ее поведению ввода-вывода. ^[8] (см. теорию вычислительного обучения ) и изучение разрешимости . вопросов ^[9]

Определение [ править ]

( Коммутативное полукольцо или rig ) — это множество R , снабженное двумя выделенными элементами $0\neq 1$ и операции сложения и умножения $\oplus$ и $\otimes$ такой, что $\oplus$ коммутативен и ассоциативен с тождеством $0$ , $\otimes$ коммутативен и ассоциативен с тождеством $1$ , $\otimes$ распределяет по $\oplus$ , а 0 – поглощающий элемент для $\otimes$ .

Взвешенный автомат над $R$ это кортеж ${\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)$ где:

$Q$ представляет собой конечное множество состояний.
$\Sigma$ является конечным алфавитом.
$\Delta \subseteq Q\times \Sigma \times R\times Q$ есть конечное множество переходов $(q,\sigma ,w,q')$ , где $\sigma$ называется персонажем и $w$ называется весом .
$I:Q\to R$ — начальная весовая функция.
$F:Q\to R$ — конечная весовая функция.

Путь на входе $w\in \Sigma ^{*}$ — конечный путь в графе, где объединение меток символов равно $w$ . Вес пути $q_{0},q_{1},\ldots ,q_{n}$ это товар( $\otimes$ ) весов вдоль пути, дополнительно умноженных на начальный и конечный веса $I(q_{0})\otimes I(q_{n})$ . Вес слова $w$ это сумма ( $\oplus$ ) весов всех путей на входе $w$ (или 0, если нет принимающих путей). Таким образом, машина определяет функцию $[\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R$ .

и детерминизм Двусмысленность

С $\Delta$ представляет собой набор переходов, взвешенные автоматы допускают несколько переходов (или путей) в одной входной строке. Поэтому взвешенный автомат можно считать аналогом недетерминированного конечного автомата (НКА). Как и в случае с НКА, рассматриваются ограничения весовых автоматов, соответствующие понятиям детерминированного конечного автомата и однозначного конечного автомата (детерминированные весовые автоматы и однозначные весовые автоматы соответственно).

Во-первых, предварительное определение: лежащий основе NFA в ${\mathcal {A}}$ представляет собой NFA, сформированный путем удаления всех переходов с весом $0$ а затем стираем все веса на переходах $\Delta$ , так что новое множество переходов лежит в $Q\times \Sigma \times Q$ . Начальные состояния и конечные состояния представляют собой набор состояний $q$ такой, что $I(q)\neq 0$ и $F(q)\neq 0$ , соответственно.

Взвешенный автомат является детерминированным , если базовый NFA является детерминированным и однозначным, если базовый NFA однозначен. Каждый детерминированный взвешенный автомат однозначен.

И в детерминированном, и в однозначном случаях всегда существует не более одного принимающего пути, поэтому $\oplus$ операция никогда не применяется и может быть опущена из определения.

Вариации [ править ]

Требование наличия нулевого элемента для $\oplus$ иногда опускается; в этом случае машина определяет частичную функцию из $\Sigma ^{*}$ к $R$ а не полную функцию.

Можно расширить определение, чтобы разрешить эпсилон-переходы. $(q,\epsilon ,w,q')$ , где $\epsilon$ пустая строка. В этом случае необходимо потребовать отсутствия циклов эпсилон-переходов. Это не увеличивает выразительность взвешенных автоматов. ^[2]^[10] Если эпсилон-переходы разрешены, начальные и конечные веса могут быть заменены начальными и конечными наборами состояний без потери выразительности.

Некоторые авторы опускают начальную и конечную весовые функции. $I$ и $F$ . ^[1] Вместо, $I$ и $F$ заменяются набором начальных и конечных состояний. Если эпсилон-переходы отсутствуют, это технически снижает выразительность, поскольку заставляет $[\![{\mathcal {A}}]\!](\varepsilon )$ зависеть только от количества состояний, которые являются как начальными, так и конечными.

Функцию перехода можно представить в виде матрицы $\Delta _{\sigma }\in R^{Q\times Q}$ с записями в $R$ для каждого $\sigma$ , а не набор переходов. Ввод матрицы в $(q,q')$ представляет собой сумму всех переходов, отмеченных $(q,\sigma ,q')$ . ^[2]^[11]

Некоторые авторы ограничиваются конкретными полукольцами, например $\mathbb {N}$ или $\mathbb {Z}$ , особенно при изучении результатов разрешимости. ^[1]^[9]^[4]

См. также [ править ]

Ссылки [ править ]

^ Перейти обратно: ^а ^б ^с ^д Чаттерджи, Кришненду; Хензингер, Томас А.; Отоп, Ян (2016). «Количественный монитор автоматов» . В «Сопернике», Ксавье (ред.). Статический анализ . Конспекты лекций по информатике. Том. 9837. Берлин, Гейдельберг: Springer. стр. 23–38. дои : 10.1007/978-3-662-53413-7_2 . ISBN 978-3-662-53413-7 .
^ Перейти обратно: ^а ^б ^с ^д ^Это ^ж Дросте, Манфред; Куич, Вернер; Фоглер, Хейко, ред. (2009). Справочник по взвешенным автоматам . Монографии по теоретической информатике. Серия EATCS. Бибкод : 2009hwa..book.....D . дои : 10.1007/978-3-642-01492-5 . ISBN 978-3-642-01491-8 . ISSN 1431-2654 . гл.1-4, стр.3-26, 69-71, 122-126.
^ Чан, Дэвид. «Взвешенные автоматы» (PDF) . Обработка естественного языка (CSE 40657/60657), конспекты курса, осень 2019 г. Проверено 9 ноября 2021 г.
^ Перейти обратно: ^а ^б Шютценбергер, член парламента (1 сентября 1961 г.). «Об определении семейства автоматов». Информация и контроль . 4 (2): 245–270. дои : 10.1016/S0019-9958(61)80020-X . ISSN 0019-9958 .
^ Чаттерджи, Кришненду; Хензингер, Томас А.; Отоп, Ян (14 декабря 2017 г.). «Вложенные взвешенные автоматы» . Транзакции ACM в вычислительной логике . 18 (4): 31:1–31:44. arXiv : 1504.06117 . дои : 10.1145/3152769 . ISSN 1529-3785 . S2CID 15070803 .
^ Алур, Раджив; Д'Антони, Лорис; Дешмукх, Джотирмой; Раготаман, Мукунд; Юань, Ифэй (2013). «Регулярные функции и автоматы регистрации затрат» . 2013 28-й ежегодный симпозиум ACM/IEEE по логике в информатике . стр. 13–22. дои : 10.1109/LICS.2013.65 . ISBN 978-1-4799-0413-6 . S2CID 1286659 .
^ Мори, Мехриар; Перейра, Фернандо; Райли, Майкл (1 января 2002 г.). «Взвешенные преобразователи с конечным состоянием в распознавании речи» . Компьютерная речь и язык . 16 (1): 69–88. дои : 10.1006/csla.2001.0184 . ISSN 0885-2308 .
^ Балле, Борха; Мори, Мехриар (2015). «Изучение взвешенных автоматов» . В Малетти, Андреас (ред.). Алгебраическая информатика . Конспекты лекций по информатике. Том. 9270. Чам: Springer International Publishing. стр. 1–21. дои : 10.1007/978-3-319-23021-4_1 . ISBN 978-3-319-23021-4 .
^ Перейти обратно: ^а ^б Альмагор, Шаулл; Бокер, Уди; Купферман, Орна (2011). «Что можно решить в отношении взвешенных автоматов?» . В Бултане Тевфик; Сюн, Пао-Анн (ред.). Автоматизированная технология проверки и анализа . Конспекты лекций по информатике. Том. 6996. Берлин, Гейдельберг: Springer. стр. 482–491. дои : 10.1007/978-3-642-24372-1_37 . ISBN 978-3-642-24372-1 . S2CID 10159261 .
^ Мори, Мехриар (2009), Дросте, Манфред; Куич, Вернер; Фоглер, Хейко (ред.), «Алгоритмы взвешенных автоматов» , Справочник по взвешенным автоматам , Монографии по теоретической информатике. Серия EATCS, Берлин, Гейдельберг: Springer, стр. 213–254, Bibcode : 2009hwa..book..213M , doi : 10.1007/978-3-642-01492-5_6 , ISBN 978-3-642-01492-5 , получено 11 ноября 2021 г.
^ Дросте, Манфред; Гастин, Пол (21 июня 2007 г.). «Весовые автоматы и взвешенная логика» . Теоретическая информатика . Автоматы, языки и программирование. 380 (1): 69–86. дои : 10.1016/j.tcs.2007.02.055 . ISSN 0304-3975 .

[QuantitativeAutomata-1] Перейти обратно: ^а ^б ^с ^д Чаттерджи, Кришненду; Хензингер, Томас А.; Отоп, Ян (2016). «Количественный монитор автоматов» . В «Сопернике», Ксавье (ред.). Статический анализ . Конспекты лекций по информатике. Том. 9837. Берлин, Гейдельберг: Springer. стр. 23–38. дои : 10.1007/978-3-662-53413-7_2 . ISBN 978-3-662-53413-7 .

[Handbook-2] Перейти обратно: ^а ^б ^с ^д ^Это ^ж Дросте, Манфред; Куич, Вернер; Фоглер, Хейко, ред. (2009). Справочник по взвешенным автоматам . Монографии по теоретической информатике. Серия EATCS. Бибкод : 2009hwa..book.....D . дои : 10.1007/978-3-642-01492-5 . ISBN 978-3-642-01491-8 . ISSN 1431-2654 . гл.1-4, стр.3-26, 69-71, 122-126.

[3] Чан, Дэвид. «Взвешенные автоматы» (PDF) . Обработка естественного языка (CSE 40657/60657), конспекты курса, осень 2019 г. Проверено 9 ноября 2021 г.

[Introduced-4] Перейти обратно: ^а ^б Шютценбергер, член парламента (1 сентября 1961 г.). «Об определении семейства автоматов». Информация и контроль . 4 (2): 245–270. дои : 10.1016/S0019-9958(61)80020-X . ISSN 0019-9958 .

[NWA-5] Чаттерджи, Кришненду; Хензингер, Томас А.; Отоп, Ян (14 декабря 2017 г.). «Вложенные взвешенные автоматы» . Транзакции ACM в вычислительной логике . 18 (4): 31:1–31:44. arXiv : 1504.06117 . дои : 10.1145/3152769 . ISSN 1529-3785 . S2CID 15070803 .

[CRA-6] Алур, Раджив; Д'Антони, Лорис; Дешмукх, Джотирмой; Раготаман, Мукунд; Юань, Ифэй (2013). «Регулярные функции и автоматы регистрации затрат» . 2013 28-й ежегодный симпозиум ACM/IEEE по логике в информатике . стр. 13–22. дои : 10.1109/LICS.2013.65 . ISBN 978-1-4799-0413-6 . S2CID 1286659 .

[WFST-7] Мори, Мехриар; Перейра, Фернандо; Райли, Майкл (1 января 2002 г.). «Взвешенные преобразователи с конечным состоянием в распознавании речи» . Компьютерная речь и язык . 16 (1): 69–88. дои : 10.1006/csla.2001.0184 . ISSN 0885-2308 .

[8] Балле, Борха; Мори, Мехриар (2015). «Изучение взвешенных автоматов» . В Малетти, Андреас (ред.). Алгебраическая информатика . Конспекты лекций по информатике. Том. 9270. Чам: Springer International Publishing. стр. 1–21. дои : 10.1007/978-3-319-23021-4_1 . ISBN 978-3-319-23021-4 .

[Decidability-9] Перейти обратно: ^а ^б Альмагор, Шаулл; Бокер, Уди; Купферман, Орна (2011). «Что можно решить в отношении взвешенных автоматов?» . В Бултане Тевфик; Сюн, Пао-Анн (ред.). Автоматизированная технология проверки и анализа . Конспекты лекций по информатике. Том. 6996. Берлин, Гейдельберг: Springer. стр. 482–491. дои : 10.1007/978-3-642-24372-1_37 . ISBN 978-3-642-24372-1 . S2CID 10159261 .

[10] Мори, Мехриар (2009), Дросте, Манфред; Куич, Вернер; Фоглер, Хейко (ред.), «Алгоритмы взвешенных автоматов» , Справочник по взвешенным автоматам , Монографии по теоретической информатике. Серия EATCS, Берлин, Гейдельберг: Springer, стр. 213–254, Bibcode : 2009hwa..book..213M , doi : 10.1007/978-3-642-01492-5_6 , ISBN 978-3-642-01492-5 , получено 11 ноября 2021 г.

[11] Дросте, Манфред; Гастин, Пол (21 июня 2007 г.). «Весовые автоматы и взвешенная логика» . Теоретическая информатика . Автоматы, языки и программирование. 380 (1): 69–86. дои : 10.1016/j.tcs.2007.02.055 . ISSN 0304-3975 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Определение [ править ]

и детерминизм Двусмысленность ​

Вариации [ править ]

См. также [ править ]

Ссылки [ править ]

и детерминизм Двусмысленность