Popisná složitost formálních systémů - Descriptional Complexity of Formal Systems
Popisná složitost formálních systémů | |
---|---|
Zkratka | DCFS |
Disciplína | Teorie automatů a formální jazyky |
Podrobnosti o publikaci | |
Vydavatel | Přednášky z informatiky |
Dějiny | 1999– |
Frekvence | roční |
DCFS, Mezinárodní seminář o popisné složitosti formálních systémů je roční akademická konference v oblasti počítačová věda.
Počínaje vydáním 2011 se v sérii objevuje sborník workshopu Přednášky z informatiky. Již od samého začátku jsou rozšířené verze vybraných příspěvků vydávány jako speciální čísla časopisu International Journal of Foundations of Computer Science, Journal of Automata, Languages and Combinatorics, z Teoretická informatika a Informace a výpočet V roce 2002 byl DCFS výsledkem sloučení workshopů DCAGRS (Popisná složitost automatů, gramatik a souvisejících struktur) a FDSR (Formální popisy a spolehlivost softwaru). Workshop je často spojován s mezinárodními konferencemi v příbuzných oborech, jako např ICALP, DLT a CIAA.
Témata workshopu
Typická témata zahrnují:
- různá opatření popisná složitost automatů, gramatik, jazyků a souvisejících systémů
- kompromisy mezi popisnou složitostí a režimem provozu
- složitost obvodu booleovských funkcí a souvisejících opatření
- stručnost popisu (konečných) objektů
- stavová složitost konečných automatů
- složitost popisu v prostředích ohraničených zdroji nebo strukturou
- strukturální složitost
- popisná složitost formálních systémů pro aplikace (např. spolehlivost softwaru, testování softwaru a hardwaru, modelování přirozených jazyků)
- aspekty složitosti popisu přírodně motivovaných (bioinspirovaných) architektur a nekonvenčních modelů výpočetní techniky
- Složitost Kolmogorov – Chaitin a popisná složitost
Témata konference se proto překrývají s tématy konference Mezinárodní federace pro zpracování informací Pracovní skupina 1.2 popisná složitost.
Význam
V průzkumu o popisné složitosti Holzer & Kutrib (2010) uvádí, že „od více než deseti let workshop o„ popisné složitosti formálních systémů “(DCFS) [...] podstatně přispěl k rozvoji [své] oblasti výzkumu.“ V přednášce u příležitosti 10. výročí workshopu Dassow (2009) poskytl přehled o trendech a směrech ve výzkumných dokumentech prezentovaných na DCFS.
Historie workshopu
Od roku 2006 je předsedou řídícího výboru série seminářů DCFS Giovanni Pighizzini.
Základní informace o každé události DCFS, stejně jako o jejích předchůdcích, DCAGRS a FSDR, jsou uvedeny v následující tabulce.
událost | Umístění | PC židle | Řízení | Speciální problém |
---|---|---|---|---|
1. DCAGRS 1999 | Magdeburg, Německo | Jürgen Dassow Detlef Wotschke | Journal of Automata, Languages and Combinatorics 5 (3), 2000 | |
2. DCAGRS 2000 | Londýn, Ontario, Kanada | Helmut Jürgensen | Journal of Automata, Languages and Combinatorics 6 (4), 2001 | |
3. DCAGRS 2001 | Vídeň, Rakousko | Jürgen Dassow Detlef Wotschke | Journal of Automata, Languages and Combinatorics 7 (4), 2002 | |
1. FSDR 1998 | Paderborn, Německo | |||
2. FSDR 1999 | Boca Raton, Florida, USA | |||
3. FSDR 2000 | San Jose, Kalifornie, USA | |||
4. DCFS 2002 | Londýn, Ontario, Kanada | Jürgen Dassow Helmut Jürgensen Detlef Wotschke | Journal of Automata, Languages and Combinatorics 9 (2/3), 2004 | |
5. DCFS 2003 | Budapešť, Maďarsko | Erzsébet Csuhaj-Varjú Chandra Kintala Detlef Wotschke | Theoretical Computer Science 330 (2), 2005 | |
6. DCFS 2004 | Londýn, Ontario, Kanada | Lucian Ilie Detlef Wotschke | International Journal of Foundations of Computer Science 16 (5), 2005 | |
7. DCFS 2005 | Como, Itálie | Giovanni Pighizzini Detlef Wotschke | Journal of Automata, Languages and Combinatorics 12 (1/2), 2007 | |
8. DCFS 2006 | Las Cruces, Nové Mexiko, USA | Hing Leung Giovanni Pighizzini | Theoretical Computer Science 387 (2), 2007 | |
9. DCFS 2007 | Vysoké Tatry, Slovensko | Viliam Geffert Giovanni Pighizzini | International Journal of Foundations of Computer Science 19 (4), 2008 | |
10. DCFS 2008 | Charlottetown, Kanada | Cezar Câmpeanu Giovanni Pighizzini | Theoretical Computer Science 410 (35), 2009. | |
11. DCFS 2009 | Magdeburg, Německo | Jürgen Dassow Giovanni Pighizzini | EPTCS 3 | Journal of Automata, Languages and Combinatorics, 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 | Giessen, Německo | Markus Holzer Martin Kutrib Giovanni Pighizzini | LNCS 6808 | Theoretical Computer Science, 449, 2012 |
14. DCFS 2012 | Braga, Portugalsko | Martin Kutrib Nelma Moreira Rogério Reis | LNCS 7386 | Journal of Automata, Languages and Combinatorics, 17 (2-4), 2012 |
15. DCFS 2013 | Londýn, Ontario, Kanada | Helmut Jürgensen Rogério Reis | LNCS 8031 | International Journal of Foundations of Computer Science, 25 (7), 2014 |
16. DCFS 2014 | Turku, Finsko | Helmut Jürgensen Juhani Karhumäki Alexander Okhotin | LNCS 8614 | Theoretical Computer Science, 610, 2016 |
17. DCFS 2015 | Waterloo, Ontario, Kanada. | Alexander Okhotin Jeffrey O. Shallit | LNCS 9118 | Zobrazí se informace a výpočet |
18. DCFS 2016 | Bukurešť, Rumunsko | Cezar Câmpeanu Jeffrey O. Shallit | LNCS 9777 | Časopis automatů, jazyků a kombinatoriky |
19. DCFS 2017 | Milán, Itálie | Cezar Câmpeanu Giovanni Pighizzini |
Viz také
- The seznam konferencí o informatice obsahuje další akademické konference v informatice.
Reference
- Bianca Truthe: „Zpráva o DCFS 2008.“ Bulletin EATCS 96: 160-161, říjen 2008. Online vydání[trvalý mrtvý odkaz ] přístup 9. února 2009.
- Jürgen Dassow: „10 let DCFS.“ Přednáška se konala na 11. DCFS v Magdeburgu v Německu, 6. – 9. Července 2009.
- Ian McQuillan: „Zpráva o DCFS 2009.“ Bulletin EATCS 99: 185-187, říjen 2009. Online vydání přístup 24. listopadu 2009.
- Elektronické sborníky z teoretické informatiky, oficiální webové stránky.
- Holzer, Markus; Kutrib, Martin (2010), „Popisná složitost - úvodní průzkum“, v Martín-Vide, Carlos (ed.), Vědecké aplikace jazykových metod Matematika, výpočetní technika, jazyk a život: Hranice v matematické lingvistice a teorie jazyků, 2, Imperial College Press, s. 1–58, ISBN 978-1-84816-544-1, archivovány z originál (PDF) 25. března 2012, vyvoláno 16. března 2011
- McQuillan, Ian; Pighizzini, Giovanni (2010), McQuillan, Ian; Pighizzini, Giovanni (eds.), „Předmluva“, Elektronické řízení v teoretické informatice, 31, arXiv:1008.1270, doi:10.4204 / EPTCS.31
- Andreas Malcher: „Zpráva o DCFS 2012.“ Bulletin EATCS 108: 168-169, říjen 2012. Online vydání.