Современные проблемы информатики Лекция 2 Алгебра поведений

Август 24, 2022

Главная
Информатика
Современные проблемы информатики Лекция 2 Алгебра поведений

Содержание

2. Что такое поведение? (инвариант бисимуляционной эквивалентности) 1.Domain theory approach (S.Abramsky 1991) 2.ACP with recursion (J.A.Bergstra and
3. Алгебра поведений Два сорта: U – поведения A – действия Сигнатура: префиксинг a.u недетерминированный выбор u
4. Монотонность
5. Непрерывность Направленное множество Наименьшая верхняя грань Непрерывность
6. Монотонность следует из непрерывности
7. Поведение есть элемент алгебры поведений ⊥ Δ Δ Δ a a b a b a a
8. Как построить алгебру всех поведений произвольных систем над множеством действий А? Алгебра конечных поведений Алгебра поведений
9. Алгебра конечных поведений Ffin(A) Порождается терминальными константами 0, Состоит из выражений в сигнатуре +, (().()) Отношение
10. Каноническая форма I – конечное множество индексов, Если все ai. ui различны и ui представлены в
11. Критерий аппроксимации Индукция по высоте u
12. Ffin(A) есть инициальная алгебра поведений Антисимметричность (индукция) Свободные алгебры поведений Ffin(A,X)
13. Алгебра поведений конечной высоты I произвольное множество (может быть пустое) Критерий аппроксимации – определение. Операции:
14. Полная алгебра поведений F(A) Элементы: классы эквивалентности направленных множеств поведений конечной высоты От классов к представителям.
15. Каноническая форма в алгебре F(A) Такое представление единственно, если все различны
16. Теорема о неподвижной точке Добавление переменных:
18. Скачать презентацию

Слайд 2

Что такое поведение?
(инвариант бисимуляционной эквивалентности)
1.Domain theory approach (S.Abramsky 1991)
2.ACP

with recursion (J.A.Bergstra and J.W.Klop, 1984)
3.Coalgebraic approach (P.Aczel, 1988, later B.Jecobs and J.Rutten)
4.Continuous algebras (A.Letichevsky,D.Gilbert,1997)

В теории автоматов:
Автомат есть транзиционная система, размеченная парами вход/выход
Поведение есть автоматное отображение
Или
Автомат есть настроенная транзиционная система, размеченная
входными символами
Поведение есть язык

Слайд 3

Алгебра поведений
Два сорта:
U – поведения
A – действия
Сигнатура:
префиксинг a.u
недетерминированный выбор

u + v
константы Δ, 0, ⊥
отношение аппроксимации
Аксиомы:
аci для недетерминированного выбора
0 есть нейтральный элемент недетерминированного выбора
есть отношение частичного порядка с наименьшим элементом ⊥
Обе операции монотонны и непрерывны (сохраняют наименьшие верхние грани)

Дополнительные структуры:
Действия: комбинация действий × , невозможное и нейтральное действия
Атрибуты: функции на поведениях

Слайд 4

Монотонность

Слайд 5

Непрерывность
Направленное множество
Наименьшая верхняя грань
Непрерывность

Слайд 6

Монотонность следует из непрерывности

Слайд 7

Поведение есть элемент алгебры поведений
⊥
Δ
Δ
Δ
a
a
b
a
b
a
a
a.(a+b+⊥)+b.a.(a+a.0)
a. Δ = a

Слайд 8

Как построить алгебру всех поведений произвольных систем над множеством действий А?
Алгебра

конечных поведений
Алгебра поведений конечной высоты
Алгебра бесконечных поведений

Слайд 9

Алгебра конечных поведений Ffin(A)
Порождается терминальными константами 0,
Состоит из выражений в

сигнатуре +, (().())

Отношение аппроксимации:

Слайд 10

Каноническая форма
I – конечное множество индексов,
Если все ai. ui различны и

ui представлены в такой же
форме, то представление u единственно с точностью до
коммутативности недетерминированного выбора.

Индукция по высоте терма h(u)

u сходится, если

и расходится в противном случае

Слайд 11

Критерий аппроксимации
Индукция по высоте u

Слайд 12

Ffin(A) есть инициальная алгебра поведений
Антисимметричность
(индукция)
Свободные алгебры поведений Ffin(A,X)

Слайд 13

Алгебра поведений конечной высоты
I произвольное множество (может быть пустое)
Критерий аппроксимации

– определение. Операции:

Слайд 14

Полная алгебра поведений F(A)
Элементы: классы эквивалентности направленных
множеств поведений конечной высоты
От

классов к представителям.
Предел направленного множества направленных множеств = их объединение.
Бесконечные суммы:

Слайд 15

Каноническая форма в алгебре F(A)
Такое представление единственно, если все различны

Слайд 16

Современные проблемы информатики Лекция 2 Алгебра поведений

Содержание

Что такое поведение? (инвариант бисимуляционной эквивалентности) 1.Domain theory approach (S.Abramsky 1991)2.ACP

Алгебра поведенийДва сорта: U – поведенияA – действияСигнатура:префиксинг a.uнедетерминированный выбор

Монотонность

НепрерывностьНаправленное множествоНаименьшая верхняя граньНепрерывность

Монотонность следует из непрерывности

Поведение есть элемент алгебры поведений⊥ΔΔΔaababaaa.(a+b+⊥)+b.a.(a+a.0) a. Δ = a

Как построить алгебру всех поведений произвольных систем над множеством действий А?Алгебра

Алгебра конечных поведений Ffin(A)Порождается терминальными константами 0, Состоит из выражений в

Каноническая формаI – конечное множество индексов,Если все ai. ui различны и

Критерий аппроксимацииИндукция по высоте u

Ffin(A) есть инициальная алгебра поведенийАнтисимметричность(индукция) Свободные алгебры поведений Ffin(A,X)

Алгебра поведений конечной высотыI произвольное множество (может быть пустое) Критерий аппроксимации

Полная алгебра поведений F(A)Элементы: классы эквивалентности направленных множеств поведений конечной высотыОт

Каноническая форма в алгебре F(A)Такое представление единственно, если все различны

Теорема о неподвижной точкеДобавление переменных:

Похожие презентации