Complejidad descriptiva de los sistemas formales

DCFS , el Taller Internacional sobre Complejidad Descriptiva de Sistemas Formales, es una conferencia académica anual en el campo de la informática .

A partir de la edición de 2011, las actas del taller aparecen en la serie Lecture Notes in Computer Science . Ya desde el principio, versiones extendidas de artículos seleccionados se publican como números especiales de International Journal of Foundations of Computer Science , Journal of Automata, Languages ​​and Combinatorics , Theoretical Computer Science e Information and Computation. En 2002, DCFS fue el resultado de la fusión de los talleres DCAGRS (Descriptional Complexity of Automata, Grammars and Related Structures) y FDSR (Formal Descriptions and Software Reliability). El taller suele celebrarse conjuntamente con conferencias internacionales en campos relacionados, como ICALP , DLT y CIAA .

Los temas típicos incluyen:

• diversas medidas de complejidad descriptiva de autómatas, gramáticas, lenguajes y sistemas relacionados.
• compensaciones entre la complejidad descriptiva y el modo de operación
• Complejidad de circuitos de funciones booleanas y medidas relacionadas
• concisión en la descripción de objetos (finitos)
• complejidad de estados de autómatas finitos
• complejidad descriptiva en entornos con recursos limitados o con estructura limitada
• complejidad estructural
• Complejidad descriptiva de sistemas formales para aplicaciones (por ejemplo, fiabilidad del software, pruebas de software y hardware, modelado de lenguajes naturales).
• Aspectos de complejidad descriptiva de arquitecturas inspiradas en la naturaleza (bioinspiradas) y modelos de computación no convencionales.
• Complejidad de Kolmogorov-Chaitin y complejidad descriptiva

Por lo tanto, los temas de la conferencia coinciden con los del Grupo de Trabajo 1.2 de la Federación Internacional para el Procesamiento de la Información sobre complejidad descriptiva .

En un estudio sobre complejidad descriptiva, Holzer y Kutrib (2010) afirman que "desde hace más de una década, el Taller sobre 'Complejidad Descriptiva de Sistemas Formales' (DCFS) [...] ha contribuido sustancialmente al desarrollo de su campo de investigación". En una charla con motivo del décimo aniversario del taller, Dassow (2009) ofreció una visión general de las tendencias y direcciones de los trabajos de investigación presentados en el DCFS.

Presidentes del Comité Directivo de la serie de talleres del DCFS:

En la siguiente tabla se incluye información básica sobre cada evento DCFS, así como sobre sus precursores, DCAGRS y FSDR.

• La lista de conferencias de informática incluye otras conferencias académicas sobre informática.

• Bianca Truthe: "Informe sobre DCFS 2008". Boletín de la EATCS 96 : 160-161, octubre de 2008. Edición en línea consultada el 9 de febrero de 2009.
• Dassow, Jürgen (2009). "10 años de DCFS" (PDF) .Charla impartida en la 11ª Conferencia DCFS en Magdeburgo, Alemania, del 6 al 9 de julio de 2009.
• Ian McQuillan: "Informe sobre DCFS 2009". Boletín de la EATCS 99 :185-187, octubre de 2009. Edición en línea consultada el 24 de noviembre de 2009.
• Actas electrónicas en informática teórica, sitio web oficial .
• Holzer, Markus; Kutrib, Martin (2010), «Complejidad descriptiva: una introducción» , en Martín-Vide, Carlos (ed.), Aplicaciones científicas de los métodos del lenguaje , Matemáticas, computación, lenguaje y vida: fronteras en lingüística matemática y teoría del lenguaje, vol.  2, Imperial College Press, pp. 1–58 , ISBN  978-1-84816-544-1Archivado del original (PDF) el 25 de marzo de 2012 , consultado el 16 de marzo de 2011.

• McQuillan, Ian; Pighizzini, Giovanni (2010), McQuillan, Ian; Pighizzini, Giovanni (eds.), "Prefacio", Electronic Proceedings in Theoretical Computer Science , 31 , arXiv : 1008.1270 , doi : 10.4204/EPTCS.31 , S2CID 24469647 
• Andreas Malcher: "Informe sobre DCFS 2012". Boletín de la EATCS 108 : 168-169, octubre de 2012. Edición en línea .

• Complejidad descriptiva de los sistemas formales: sitio web oficial