Описательная сложность формальных систем

Описательная сложность формальных систем
Аббревиатура	DCFS
Дисциплина	Теория автоматов и формальные языки
Подробности публикации
Издатель	Конспекты лекций по информатике
История	1999–
Частота	ежегодный

DCFS , Международный семинар по описанию сложности формальных систем — это ежегодная научная конференция в США. область информатики .

Начиная с издания 2011 года материалы семинара публикуются в серии « Конспекты лекций по информатике» . Уже с самого начала расширенные версии избранных статей публикуются в виде специальных выпусков Международного журнала основ компьютерных наук , Журнала автоматов, языков и комбинаторики , Теоретической информатики и Информации и вычислений. В 2002 году DCFS был результат слияния мастерских DCAGRS (Описательная сложность автоматов, грамматик и родственных структур) и FDSR (Формальные описания и надежность программного обеспечения). Семинар часто проводится одновременно с международными конференциями в смежных областях, таких как ICALP , DLT и CIAA .

Темы семинара

Типичные темы включают в себя:

• различные меры сложности описания автоматов, грамматик, языков и родственных систем
• компромисс между сложностью описания и режимом работы
• сложность схемы булевых функций и связанных с ними мер
• краткость описания (конечных) объектов
• сложность состояния конечных автоматов
• сложность описания в средах с ограниченными ресурсами или структурами
• структурная сложность
• сложность описания формальных систем для приложений (например, надежность программного обеспечения, тестирование программного и аппаратного обеспечения, моделирование естественных языков)
• аспекты сложности описания природных (биоинспирированных) архитектур и нетрадиционных моделей вычислений
• Сложность Колмогорова–Чайтина и сложность описания.

Таким образом, темы конференции совпадают с темами Международной федерации обработки информации Рабочей группы 1.2 по сложности описания .

Значение

В обзоре сложности описания Хольцер и Катриб (2010) заявляют, что «на протяжении более десяти лет Семинар по «Описательной сложности формальных систем» (DCFS) [...] внес существенный вклад в развитие [его] область исследований». В докладе по случаю 10-летия семинара Дассов (2009) дал обзор тенденций и направлений исследовательских работ, представленных на DCFS.

История мастерской

Председатели Руководящего комитета серии семинаров DCFS:

Период	Стул
1999 - 2005	Детлеф Вочке
2006 - 2017	Джованни Пигиццини
2017 -	Мартин Кутриб

Основная информация о каждом событии DCFS, а также о его предшественниках, DCAGRS и FSDR, включена в следующую таблицу.

Событие	Расположение	Стулья для ПК	Слушания	Специальный выпуск
1-й ДКАГРС 1999 г.	Магдебург, Германия	Юрген Дассов Детлеф Вочке		Журнал автоматов, языков и комбинаторики 5 (3), 2000 г.
2-й ДКАГРС 2000 г.	Лондон, Онтарио, Канада	Хельмут Юргенсен		Журнал автоматов, языков и комбинаторики 6 (4), 2001 г.
3-я ДКАГРС 2001 г.	Вена, Австрия	Юрген Дассов Детлеф Вочке		Журнал автоматов, языков и комбинаторики 7 (4), 2002 г.
1-я ФСДР 1998 г.	Падерборн, Германия
2-я ФСДР 1999 г.	Бока-Ратон, Флорида, США
3-я ФСДР 2000 г.	Сан-Хосе, Калифорния, США
4-й DCFS 2002. Архивировано 3 марта 2016 г. в Wayback Machine.	Лондон, Онтарио, Канада	Юрген Дассов Хельмут Юргенсен Детлеф Вочке		Журнал автоматов, языков и комбинаторики 9 (2/3), 2004 г.
5-я конференция DCFS 2003 г.	Будапешт, Венгрия	Эржебет Чухай-Варью Чандра Кинтала Детлеф Вочке		Теоретическая информатика 330 (2), 2005 г.
6-я конференция DCFS 2004 г.	Лондон, Онтарио, Канада	Люциан Илия Детлеф Вочке		Международный журнал основ компьютерных наук 16 (5), 2005 г.
7-я конференция DCFS 2005. Архивировано 13 ноября 2017 г. в Wayback Machine.	Комо, Италия	Джованни Пигиццини Детлеф Вочке		Журнал автоматов, языков и комбинаторики 12 (1/2), 2007 г.
8-я конференция DCFS 2006 г.	Лас-Крусес, Нью-Мексико, США	Хинг Люн Джованни Пигиццини		Теоретическая информатика 387 (2), 2007 г.
9-я конференция DCFS 2007 г.	Высокие Татры, Словакия	Вильям Гефферт Джованни Пигиццини		Международный журнал основ компьютерных наук 19 (4), 2008 г.
10-я конференция DCFS 2008 г.	Шарлоттаун, Канада	Цезарь Кампеану Джованни Пигиццини		Теоретическая информатика 410 (35), 2009.
11-я конференция DCFS 2009 г.	Магдебург, Германия	Юрген Дассов Джованни Пигиццини	ЭПТС 3	Журнал автоматов, языков и комбинаторики , 15 (1-2), 2010 г.
12-я конференция DCFS 2010 г.	Саскатун, Саскачеван, Канада	Ян Маккуиллан Джованни Пигиццини	ЭПТС 31	Международный журнал основ компьютерных наук , 23 (1), 2012 г.
13-я конференция DCFS 2011 г.	Гиссен, Германия	Маркус Хольцер Мартин Кутриб Джованни Пигиццини	ЛНКС 6808	Теоретическая информатика , 449, 2012.
14-я конференция DCFS 2012 г.	Брага, Португалия	Мартин Кутриб Нельма Морейра Рожерио Рейс	ЛНКС 7386	Журнал автоматов, языков и комбинаторики , 17(2-4), 2012 г.
15-я выставка DCFS 2013. Архивировано 5 марта 2016 г. в Wayback Machine.	Лондон, Онтарио, Канада	Хельмут Юргенсен Рожерио Рейс	ЛНКС 8031	Международный журнал основ компьютерных наук , 25 (7), 2014 г.
16-я конференция DCFS 2014 г.	Турку, Финляндия	Хельмут Юргенсен Юхани Карумаки Alexander Okhotin	ЛНКС 8614	Теоретическая информатика , 610, 2016
17-я конференция DCFS 2015 г.	Ватерлоо, Онтарио, Канада	Alexander Okhotin Джеффри О. Шалит	ЛНКС 9118	Информация и вычисления , 259(2), 2018 г.
18-я конференция DCFS 2016 г.	Бухарест, Румыния	Цезарь Кампеану Джеффри О. Шалит	ЛНКС 9777	Журнал автоматов, языков и комбинаторики , 22(1-3), 2017
19-я конференция DCFS 2017	Милан, Италия	Цезарь Кампеану Джованни Пигиццини	ЛНКС 10316	Международный журнал основ компьютерных наук , 30(6-7), 2019 г.
20-я конференция DCFS 2018 г.	Галифакс, Северная Каролина, Канада	Ставрос Константинидис Джованни Пигиццини	ЛНКС 10952	Теоретическая информатика , 798, 2019
21-я конференция DCFS 2019 г.	Кошице, Словакия	Галина Йираскова Ставрос Константинидис	ЛНКС 11612	Информация и вычисления , появится
22-я конференция DCFS 2020	Вена, Австрия (отменено)	Галина Йираскова Джованни Пигиццини	ЛНКС 12442 (сборник статей)	Журнал автоматов, языков и комбинаторики , в разработке

См. также

• Список конференций по информатике содержит и другие научные конференции по информатике.

Ссылки

• Бьянка Трут: «Отчет о DCFS за 2008 год». Бюллетень EATCS 96 : 160-161, октябрь 2008 г. Интернет-издание. по состоянию на 9 февраля 2009 г.
• Дассов, Юрген (2009). «10 лет DCFS» (PDF) . Доклад состоялся на 11-й конференции DCFS в Магдебурге, Германия, 6–9 июля 2009 г.
• Ян Маккуиллан: «Отчет о DCFS за 2009 год». Бюллетень EATCS 99 : 185-187, октябрь 2009 г. Интернет-издание по состоянию на 24 ноября 2009 г.
• Электронные труды по теоретической информатике, официальный сайт .
• Хольцер, Маркус; Кутриб, Мартин (2010), «Описательная сложность — вводный обзор» , Мартин-Виде, Карлос (редактор), « Научные применения языковых методов , математики, вычислений, языка и жизни: границы в математической лингвистике и теории языка», том. 2, Imperial College Press, стр. 1–58, ISBN.  978-1-84816-544-1 , заархивировано из оригинала (PDF) 25 марта 2012 г. , получено 16 марта 2011 г.

• Маккуиллан, Ян; Пигиццини, Джованни (2010), Маккуиллан, Ян; Пигиццини, Джованни (ред.), «Предисловие», Электронные труды по теоретической информатике , 31 , arXiv : 1008.1270 , doi : 10.4204/EPTCS.31 , S2CID   24469647
• Андреас Малчер: «Отчет о DCFS 2012». Бюллетень EATCS 108 :168-169, октябрь 2012 г. Интернет-издание .

Внешние ссылки

• Описательная сложность формальных систем: официальный сайт