形式システムの記述の複雑さ

DCFS (形式システムの記述的複雑性に関する国際ワークショップ)は、コンピュータ サイエンスの分野における毎年開催される学術会議です。

2011年版より、ワークショップの議事録はLecture Notes in Computer Scienceシリーズに掲載されています。 当初から、選ばれた論文の拡張版がInternational Journal of Foundations of Computer Science、Journal of Automata, Languages and Combinatorics、Theoretical Computer Science、Information and Computationの特別号として出版されています。 2002年に、 DCFS は DCAGRS (オートマトン、文法、および関連構造の記述的複雑性) ワークショップと FDSR (形式的記述とソフトウェアの信頼性) ワークショップが合併して誕生しました。 このワークショップは、 ICALP、DLT、CIAAなど、関連分野の国際会議と同時に開催されることがよくあります。

代表的なトピックは次のとおりです。

• オートマトン、文法、言語、および関連システムの記述の複雑さのさまざまな尺度
• 記述の複雑さと動作モードのトレードオフ
• ブール関数の回路の複雑さと関連する尺度
• （有限の）物体の記述の簡潔さ
• 有限オートマトンの状態複雑度
• 資源制限または構造制限のある環境における記述の複雑さ
• 構造の複雑さ
• アプリケーションのための形式システムの記述的複雑さ（例：ソフトウェアの信頼性、ソフトウェアとハ​​ードウェアのテスト、自然言語のモデリング）
• 自然に動機付けられた（生物に触発された）アーキテクチャと非従来型のコンピューティングモデルの記述的複雑性の側面
• コルモゴロフ・チャイティン複雑性と記述複雑性

そのため、この会議のトピックは、記述の複雑性に関する国際情報処理連盟ワーキンググループ 1.2のトピックと重複しています。

記述的複雑性に関する調査で、Holzer と Kutrib (2010) は、「10 年以上にわたり、『形式システムの記述的複雑性』(DCFS) に関するワークショップは、[...] [その] 研究分野の発展に大きく貢献してきました」と述べています。ワークショップの 10 周年を記念した講演で、Dassow (2009) は DCFS で発表された研究論文の傾向と方向性について概要を説明しました。

DCFSワークショップシリーズの運営委員会委員長:

各 DCFS イベントとその前身である DCAGRS および FSDR に関する基本情報は、次の表に示されています。

• コンピュータ サイエンス カンファレンスのリストには、コンピュータサイエンスの他の学術カンファレンスも含まれています。

• Bianca Truthe：「DCFS 2008 に関する報告」。Bulletin of the EATCS 96 :160-161、2008 年 10 月。オンライン版^{[永久リンク切れ‍ ]} 2009 年 2 月 9 日にアクセス。
• ダッソウ、ユルゲン (2009)。 「10年間のDCFS」（PDF）。2009 年 7 月 6 日から 9 日までドイツのマクデブルクで開催された第 11 回 DCFS で行われた講演。
• Ian McQuillan: 「DCFS 2009 に関するレポート」Bulletin of the EATCS 99 :185-187、2009 年 10 月。オンライン版は 2009 年 11 月 24 日にアクセスしました。
• Electronic Proceedings in Theoretical Computer Science の公式ウェブサイト。
• Holzer, Markus; Kutrib, Martin (2010)、「記述的複雑性 - 入門調査」、Martín-Vide, Carlos (編)、『言語手法、数学、コンピューティング、言語、および生命の科学的応用: 数理言語学と言語理論のフロンティア』第 2 巻、Imperial College Press、pp. 1–58、ISBN 978-1-84816-544-1、 2012年3月25日時点のオリジナル（PDF）からアーカイブ、2011年3月16日閲覧

• McQuillan, Ian; Pighizzini, Giovanni (2010)、McQuillan, Ian; Pighizzini, Giovanni (編)、「序文」、Electronic Proceedings in Theoretical Computer Science、31、arXiv : 1008.1270、doi :10.4204/EPTCS.31、S2CID  24469647
• Andreas Malcher: 「DCFS 2012 に関するレポート」Bulletin of the EATCS 108 :168-169、2012 年 10 月。オンライン版。

• 形式システムの記述的複雑性: 公式ウェブサイト