Beschreibungskomplexität formaler Systeme
DCFS, das Internationaler Workshop zur Beschreibungskomplexität formaler Systeme ist eine jährliche wissenschaftliche Konferenz im Bereich der Informatik.
Ab der Ausgabe 2011 erscheint der Tagungsband in der Reihe Lecture Notes in Computer Science. Bereits seit Beginn erscheinen erweiterte Versionen ausgewählter Arbeiten als Sonderhefte des International Journal of Foundations of Computer Science, des Journal of Automata, Languages and Combinatorics, of Theoretical Computer Science und of Information and Computation 2002 war DCFS die Ergebnis des Zusammenschlusses der Werkstätten DCAGRS (Descriptional Complexity of Automata, Grammars and Related Structures) und FDSR (Formal Descriptions and Software Reliability). Der Workshop wird oft mit internationalen Konferenzen in verwandten Bereichen wie ICALP, DLT und CIAA zusammengeführt.
Themen des Workshops[edit]
Typische Themen sind:
- verschiedene Maße der Beschreibungskomplexität von Automaten, Grammatiken, Sprachen und verwandten Systemen
- Kompromisse zwischen Beschreibungskomplexität und Funktionsweise
- Schaltungskomplexität boolescher Funktionen und zugehörige Maßnahmen
- Prägnanz der Beschreibung von (endlichen) Objekten
- Zustandskomplexität endlicher Automaten
- Beschreibungskomplexität in ressourcen- oder strukturbegrenzten Umgebungen
- strukturelle Komplexität
- Beschreibungskomplexität formaler Systeme für Anwendungen (zB Softwarezuverlässigkeit, Software- und Hardwaretest, Modellierung natürlicher Sprachen)
- Beschreibungskomplexitätsaspekte naturmotivierter (bioinspirierter) Architekturen und unkonventioneller Computermodelle
- Kolmogorov-Chaitin-Komplexität und Beschreibungskomplexität
Damit überschneiden sich die Themen der Konferenz mit denen der International Federation for Information Processing Working Group 1.2 zur Beschreibungskomplexität.
Bedeutung[edit]
In einer Umfrage zur Beschreibungskomplexität stellen Holzer & Kutrib (2010) fest, dass “seit mehr als einem Jahrzehnt der Workshop ‘Descriptional Complexity of Formal Systems’ (DCFS), […] hat wesentlich zur Entwicklung von [its] Forschungsfeld.” In einem Vortrag anlässlich des 10-jährigen Bestehens des Workshops, Dassow (2009) harvtxt-Fehler: kein Ziel: CITEREFDassow2009 (Hilfe) gab einen Überblick über Trends und Richtungen in Forschungsarbeiten, die am DCFS präsentiert wurden.
Geschichte der Werkstatt[edit]
Vorsitzende des Lenkungsausschusses der DCFS-Workshop-Reihe:
Grundlegende Informationen zu jedem DCFS-Ereignis sowie zu seinen Vorläufern DCAGRS und FSDR sind in der folgenden Tabelle enthalten.
| Vorfall | Standort | PC-Stühle | Verfahren | Sonderausgabe |
|---|---|---|---|---|
| 1. DCAGRS 1999 | Magdeburg, Deutschland | Jürgen Dassow Detlef Wotschke |
Zeitschrift für Automaten, Sprachen und Kombinatorik 5(3), 2000 | |
| 2. DCAGRS 2000 | London, Ontario, Kanada | Helmut Jürgensen | Zeitschrift für Automaten, Sprachen und Kombinatorik 6(4), 2001 | |
| 3. DCAGRS 2001 | Wien, Österreich | Jürgen Dassow Detlef Wotschke |
Zeitschrift für Automaten, Sprachen und Kombinatorik 7(4), 2002 | |
| 1. FSDR 1998 | Paderborn, Deutschland | |||
| 2. FSDR 1999 | Boca Raton, Florida, USA | |||
| 3. FSDR 2000 | San Jose, Kalifornien, USA | |||
| 4. DCFS 2002 | London, Ontario, Kanada | Jürgen Dassow Helmut Jürgensen Detlef Wotschke |
Zeitschrift für Automaten, Sprachen und Kombinatorik 9(2/3), 2004 | |
| 5. DCFS 2003 | Budapest, Ungarn | Erzsébet Csuhaj-Varjú Chandra Kintala Detlef Wotschke |
Theoretische Informatik 330(2), 2005 | |
| 6. DCFS 2004 | London, Ontario, Kanada | Lucian Ilie Detlef Wotschke |
International Journal of Foundations of Computer Science 16(5), 2005 | |
| 7. DCFS 2005 | Como, Italien | Giovanni Pighizzini Detlef Wotschke |
Journal of Automata, Languages and Combinatorics 12(1/2), 2007 | |
| 8. DCFS 2006 | Las Cruces, New Mexico, USA | Hing Leung Giovanni Pighizzini |
Theoretische Informatik 387(2), 2007 | |
| 9. DCFS 2007 | Hohe Tatra, Slowakei | Viliam Geffert Giovanni Pighizzini |
International Journal of Foundations of Computer Science 19(4), 2008 | |
| 10. DCFS 2008 | Charlottetown, Kanada | Cezar Campeanu Giovanni Pighizzini |
Theoretische Informatik 410(35), 2009. | |
| 11. DCFS 2009 | Magdeburg, Deutschland | Jürgen Dassow Giovanni Pighizzini |
EPTCS 3 | Zeitschrift für Automaten, Sprachen und Kombinatorik, 15(1-2), 2010 |
| 12. DCFS 2010 | Saskatoon, Saskatchewan, Kanada | Ian McQuillan Giovanni Pighizzini |
EPTCS 31 | International Journal of Foundations of Computer Science, 23(1), 2012 |
| 13. DCFS 2011 | Gießen, Deutschland | Markus Holzer Martin Kutrib Giovanni Pighizzini |
LNCS 6808 | Theoretische Informatik, 449, 2012 |
| 14. DCFS 2012 | Braga, Portugal | Martin Kutrib Nelma Moreira Rogério Reis |
LNCS 7386 | Zeitschrift für Automaten, Sprachen und Kombinatorik, 17(2-4), 2012 |
| 15. DCFS 2013 | London, Ontario, Kanada | Helmut Jürgensen Rogério Reis |
LNCS 8031 | International Journal of Foundations of Computer Science, 25(7), 2014 |
| 16. DCFS 2014 | Turku, Finnland | Helmut Jürgensen Juhani Karhumäki Alexander Ochotin |
LNCS 8614 | Theoretische Informatik, 610, 2016 |
| 17. DCFS 2015 | Waterloo, Ontario, Kanada | Alexander Ochotin Jeffrey O. Shallit |
LNCS 9118 | Information und Berechnung, 259(2), 2018 |
| 18. DCFS 2016 | Bukarest, Rumänien | Cezar Campeanu Jeffrey O. Shallit |
LNCS 9777 | Zeitschrift für Automaten, Sprachen und Kombinatorik, 22(1-3), 2017 |
| 19. DCFS 2017 | Mailand, Italien | Cezar Campeanu Giovanni Pighizzini |
LNCS 10316 | International Journal of Foundations of Computer Science, 30(6-7), 2019 |
| 20. DCFS 2018 | Halifax, NS, Kanada | Stavros Konstantinidis Giovanni Pighizzini |
LNCS 10952 | Theoretische Informatik, 798, 2019 |
| 21. DCFS 2019 | Košice, Slowakei | Galina Jirásková Stavros Konstantinidis |
LNCS 11612 | Information und Berechnung, zu erscheinen |
| 22. DCFS 2020 | Wien, Österreich (abgesagt) | Galina Jirásková Giovanni Pighizzini |
LNCS 12442 (gesammelte Papiere) |
Journal of Automata, Languages and Combinatorics, in Arbeit |
Siehe auch[edit]
Verweise[edit]
- Bianca Truthe: “Bericht über DCFS 2008.” Bulletin des EATCS 96:160-161, Oktober 2008. Online-Ausgabe[permanent dead link] abgerufen am 9. Februar 2009.
- Jürgen Dassow: “10 Jahre DCFS.” Vortrag auf der 11. DCFS in Magdeburg, 6.-9. Juli 2009.
- Ian McQuillan: “Bericht über DCFS 2009.” Bulletin des EATCS 99:185-187, Oktober 2009. Online-Ausgabe abgerufen am 24.11.2009.
- Elektronische Proceedings in Theoretischer Informatik, offizielle Website.
- Holzer, Markus; Kutrib, Martin (2010), “Beschreibungskomplexität – Eine einführende Umfrage”, in Martin-Vide, Carlos (Hrsg.), Wissenschaftliche Anwendungen von Sprachmethoden, Mathematik, Informatik, Sprache und Leben: Frontiers in Mathematical Linguistics and Language Theory, 2, Imperial College Press, S. 1–58, ISBN 978-1-84816-544-1, archiviert von das Original (PDF) am 25. März 2012, abgerufen 16. März 2011
- McQuillan, Ian; Pighizzini, Giovanni (2010), McQuillan, Ian; Pighizzini, Giovanni (Hrsg.), “Vorwort”, Elektronische Proceedings in Theoretischer Informatik, 31, arXiv:1008.1270, doi:10.4204/EPTCS.31
- Andreas Malcher: “Bericht zum DCFS 2012.” Bulletin des EATCS 108:168-169, Oktober 2012. Online-Ausgabe.
Externe Links[edit]
Recent Comments