https://iccl.inf.tu-dresden.de/w/api.php?action=feedcontributions&feedformat=atom&user=Timm+Spork 2026-10-03T10:46:17Z Benutzerbeiträge MediaWiki 1.43.1 https://iccl.inf.tu-dresden.de/w/index.php?title=Proseminar_Theoretische_Informatik_(WS2026)&diff=45101 2026-10-02T08:45:37Z

<p>Timm Spork: </p> <hr /> <div>{{Vorlesung<br /> |Title=Proseminar „Theoretische Informatik“<br /> |Title_EN=Proseminar “Theoretische Informatik”<br /> |Research group=Algebraische und logische Grundlagen der Informatik<br /> |Lecturers=Sascha Klüppelholz<br /> |Language=DE<br /> |Term=WS<br /> |Year=2026<br /> |Module=INF-25-Ba-WIA<br /> |SWSLecture=0<br /> |SWSExercise=2<br /> |SWSPractical=0<br /> |Description=Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.<br /> <br /> === Anmeldung ===<br /> <br /> Für die Teilnahme ist eine Registrierung [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] bis zum 12. Oktober erforderlich.<br /> <br /> === Voraussetzungen ===<br /> <br /> Neben dem Interesse an Theoretischer Informatik setzt das Proseminar solide Kenntnisse in den Gebieten Algorithmen und Datenstrukturen sowie Mathematik im Umfang der ersten zwei Studiensemester voraus.<br /> <br /> === Termine === <br /> <br /> Die Auftaktveranstaltung findet am 16. Oktober von 11:10 Uhr - 12:40 Uhr statt. Details werden allen fristgerecht in Opal eingeschriebenen Teilnehmer:innen per E-Mail mitgeteilt. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugewiesen. Danach wird das weitere Vorgehen individuell mit dem Betreuer besprochen.<br /> <br /> Die geforderten Vorträge und Fragenrunden werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Die genauen Termine werden zu einem späteren Zeitpunkt bekanntgegeben.<br /> <br /> === Prüfungsleistung ===<br /> <br /> '''Bachelor Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)<br /> <br /> '''Bachelor Angewandte Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)<br /> <br /> '''Diplom Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)<br /> <br /> Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine mündliche Fragenrunde (15 Minuten) vorgesehen.<br /> <br /> === Kontakt ===<br /> <br /> Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].<br /> <br /> |Description_EN=<br /> {{MissingTranslation|Language=en}}<br /> <br /> Das Thema des Proseminars ist die Analyse von Algorithmen. Es werden u. a. Algorithmen aus den Büchern [https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ „Introduction to Algorithms“] von Cormen, Leiserson, Rivest und Stein, [https://www-cs-faculty.stanford.edu/~knuth/gkp.html „Concrete Mathematics“] von Graham, Knuth und Patashnik sowie [https://diestel-graph-theory.com/german/index.html „Graphentheorie“] von Diestel betrachtet.<br /> <br /> === Registration ===<br /> <br /> Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075267 via Opal] is required until October 12.<br /> <br /> === Prerequisites ===<br /> <br /> Besides an interest in theoretical computer science, the ''Proseminar'' requires solid foundations in algorithms and data structures, as well as mathematics as covered in the first two semesters of the study program.<br /> <br /> === Dates === <br /> <br /> The initial meeting will be held on October 16th from 11:10am - 12:40pm. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.<br /> <br /> The required presentations and question-and-answer sessions will be held en bloc between January and March 2027. The specific dates will be announced later.<br /> <br /> === Examination ===<br /> <br /> '''Bachelor Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)<br /> <br /> '''Bachelor Angewandte Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)<br /> <br /> '''Diplom Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)<br /> <br /> The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).<br /> <br /> === Contact ===<br /> <br /> In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].<br /> <br /> }}</div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Proseminar_Bin%C3%A4re_Entscheidungsgraphen_(WS2026)&diff=45100 2026-10-02T08:40:56Z

<p>Timm Spork: </p> <hr /> <div>{{Vorlesung<br /> |Title=Proseminar „Binäre Entscheidungsgraphen“<br /> |Title_EN=Proseminar “Binäre Entscheidungsgraphen”<br /> |Research group=Algebraische und logische Grundlagen der Informatik<br /> |Lecturers=Sascha Klüppelholz<br /> |Language=DE<br /> |Term=WS<br /> |Year=2026<br /> |Module=INF-25-Ba-WIA<br /> |SWSLecture=0<br /> |SWSExercise=2<br /> |SWSPractical=0<br /> |Description=Das Thema des Proseminars sind binäre Entscheidungsgraphen (engl. ''Binary Decision Diagrams'', kurz BDDs). Diese wurden erstmals von Lee und Akers zur Darstellung von Schaltfunktionen vorgestellt. Heute werden verschiedene Varianten von ''ordered BDDs (OBDDs)'' in zahlreichen Verifikationswerkzeugen und Model Checkern wie z. B. nuSMV oder Prism als Datenstruktur zur effizienten Speicherung und Analyse von Systemmodellen eingesetzt.<br /> <br /> Die individuell zu bearbeitenden Seminarthemen befassen sich mit den theoretischen Grundlagen binärer Entscheidungsgraphen. Insbesondere sollen die wichtigsten Operatoren und Algorithmen auf BDDs vorgestellt und hinsichtlich ihrer theoretischen Komplexität untersucht werden.<br /> <br /> === Anmeldung ===<br /> <br /> Für die Teilnahme ist eine Registrierung [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075268 via Opal] bis zum 12. Oktober erforderlich.<br /> <br /> === Voraussetzungen ===<br /> <br /> Neben dem Interesse an Theoretischer Informatik setzt das Proseminar solide Kenntnisse in den Gebieten Algorithmen und Datenstrukturen sowie Mathematik im Umfang der ersten zwei Studiensemester voraus.<br /> <br /> === Termine === <br /> <br /> Die Auftaktveranstaltung findet am 16. Oktober von 09:20 Uhr - 10:50 Uhr statt. Details werden allen fristgerecht in Opal eingeschriebenen Teilnehmer:innen per E-Mail mitgeteilt. Anschließend wird allen Teilnehmer:innen je ein Thema und ein Betreuer zugewiesen. Danach wird das weitere Vorgehen individuell mit dem Betreuer besprochen.<br /> <br /> Die geforderten Vorträge und Fragenrunden werden als Blockveranstaltung im Zeitraum Januar–März 2027 stattfinden. Die genauen Termine werden zu einem späteren Zeitpunkt bekanntgegeben.<br /> <br /> === Prüfungsleistung ===<br /> <br /> '''Bachelor Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)<br /> <br /> '''Bachelor Angewandte Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)<br /> <br /> '''Diplom Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: Komplexe Leistung (60 Stunden)<br /> <br /> Als Komplexe Leistung ist ein Folienvortrag (25 Minuten) sowie eine mündliche Fragenrunde (15 Minuten) vorgesehen.<br /> <br /> === Kontakt ===<br /> <br /> Bei organisatorischen Fragen senden Sie eine E-Mail an [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].<br /> <br /> |Description_EN=<br /> {{MissingTranslation|Language=en}}<br /> <br /> Das Thema des Proseminars sind binäre Entscheidungsgraphen (engl. ''Binary Decision Diagrams'', kurz BDDs). Diese wurden erstmals von Lee und Akers zur Darstellung von Schaltfunktionen vorgestellt. Heute werden verschiedene Varianten von ''ordered BDDs (OBDDs)'' in zahlreichen Verifikationswerkzeugen und Model Checkern wie z. B. nuSMV oder Prism als Datenstruktur zur effizienten Speicherung und Analyse von Systemmodellen eingesetzt.<br /> <br /> Die individuell zu bearbeitenden Seminarthemen befassen sich mit den theoretischen Grundlagen binärer Entscheidungsgraphen. Insbesondere sollen die wichtigsten Operatoren und Algorithmen auf BDDs vorgestellt und hinsichtlich ihrer theoretischen Komplexität untersucht werden.<br /> <br /> === Registration ===<br /> <br /> Registration [https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/55848075268 via Opal] is required until October 12.<br /> <br /> === Prerequisites ===<br /> <br /> Besides an interest in theoretical computer science, the ''Proseminar'' requires solid foundations in algorithms and data structures, as well as mathematics as covered in the first two semesters of the study program.<br /> <br /> === Dates === <br /> <br /> The initial meeting will be held on October 16th from 09:20am - 10:50am. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.<br /> <br /> The required presentations and question-and-answer sessions will be held en bloc between January and March 2027. The specific dates will be announced later.<br /> <br /> === Examination ===<br /> <br /> '''Bachelor Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)<br /> <br /> '''Bachelor Angewandte Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)<br /> <br /> '''Diplom Informatik (PO 2025)'''<br /> * {{ModuleLink|INF-25-Ba-WIA}}: ''Komplexe Leistung'' (60 hours)<br /> <br /> The ''Komplexe Leistung'' (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).<br /> <br /> === Contact ===<br /> <br /> In case of organizational questions, please send an e-mail to [mailto:studies_alg@mailbox.tu-dresden.de studies_alg@mailbox.tu-dresden.de].<br /> <br /> }}</div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Inproceedings3470&diff=45099 2026-10-02T06:47:47Z

<p>Timm Spork: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Christel |ErsterAutorNachname=Baier |FurtherAuthors=Sascha Klüppelholz; Timm Spork }} {{Inproceedings |Referiert=1 |Title=Probabilistic Model Checking via Families of Deterministic and Unambiguous Finite Automata |To appear=0 |Year=2026 |Month=August |Booktitle=37th International Conference on Concurrency Theory (CONCUR 2026) |Pages=15:1 - 15:19 |Publisher=Schloss Dagstuhl- Leibniz-Zentrum für Informatik |E…“</p> <hr /> <div>{{Publikation Erster Autor<br /> |ErsterAutorVorname=Christel<br /> |ErsterAutorNachname=Baier<br /> |FurtherAuthors=Sascha Klüppelholz; Timm Spork<br /> }}<br /> {{Inproceedings<br /> |Referiert=1<br /> |Title=Probabilistic Model Checking via Families of Deterministic and Unambiguous Finite Automata<br /> |To appear=0<br /> |Year=2026<br /> |Month=August<br /> |Booktitle=37th International Conference on Concurrency Theory (CONCUR 2026)<br /> |Pages=15:1 - 15:19<br /> |Publisher=Schloss Dagstuhl- Leibniz-Zentrum für Informatik<br /> |Editor=Ana Sokolova, Patrick Totzke<br /> |Series=Leibniz International Proceedings in Informatics (LIPIcs)<br /> |Volume=391<br /> }}<br /> {{Publikation Details<br /> |Abstract=Families of deterministic finite automata (FDFA) have been introduced as a concise automaton model that characterizes ω-regular languages by processing their ultimately periodic words. FDFA are known to enjoy many good properties and can be exponentially more succinct than deterministic ω-automata with Rabin, Streett or parity acceptance. This paper addresses two main questions: (1) Are FDFA suitable for probabilistic model checking purposes? and (2) Is it possible to obtain an even more compact representation of ω-regular languages by allowing the components of an FDFA to be unambiguous instead of deterministic? Question (1) is answered in the affirmative by presenting the first polynomial-time algorithm for computing the probability that a discrete-time Markov chain satisfies an ω-regular property represented as an FDFA. Question (2) is motivated by the fact that unambiguous finite automata may require exponentially fewer states than deterministic ones. This paper introduces a model of families of unambiguous finite automata (FUFA) that captures the class of ω-regular languages. FUFA can be exponentially more succinct than both FDFA and unambiguous Büchi automata, and there is a single-exponential translation from linear temporal logic (LTL) to FUFA. This stands in contrast to a double-exponential lower bound for the translation from LTL to FDFA. Moreover, the polynomial-time probabilistic model checking algorithm for discrete-time Markov chains against FDFA-specifications is extended to the case where the property is represented by an FUFA with a deterministic leading automaton.<br /> |ISBN=978-3-95977-447-5<br /> |ISSN=1868-8969<br /> |Download=LIPIcs.CONCUR.2026.15.pdf<br /> |DOI Name=10.4230/LIPIcs.CONCUR.2026.15<br /> |Projekt=CPEC, CeTI, SECAI<br /> |Forschungsgruppe=Algebraische und logische Grundlagen der Informatik<br /> |BibTex=@InProceedings{baier_et_al:LIPIcs.CONCUR.2026.15,<br /> author = {Baier, Christel and Kl\&quot;{u}ppelholz, Sascha and Spork, Timm},<br /> title = {{Probabilistic Model Checking via Families of Deterministic and Unambiguous Finite Automata}},<br /> booktitle = {37th International Conference on Concurrency Theory (CONCUR 2026)},<br /> pages = {15:1--15:19},<br /> series = {Leibniz International Proceedings in Informatics (LIPIcs)},<br /> ISBN = {978-3-95977-447-5},<br /> ISSN = {1868-8969},<br /> year = {2026},<br /> volume = {391},<br /> editor = {Sokolova, Ana and Totzke, Patrick},<br /> publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\&quot;u}r Informatik},<br /> address = {Dagstuhl, Germany},<br /> URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.15},<br /> URN = {urn:nbn:de:0030-drops-273461},<br /> doi = {10.4230/LIPIcs.CONCUR.2026.15},<br /> annote = {Keywords: Families of Finite Automata, FDFA, Unambiguous Automata, Discrete-time Markov Chains, Probabilistic Model Checking, Verification}<br /> }<br /> }}</div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Datei:LIPIcs.CONCUR.2026.15.pdf&diff=45098 2026-10-02T06:43:27Z

<p>Timm Spork: </p> <hr /> <div></div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Inproceedings3441&diff=43450 2025-10-30T11:59:23Z

<p>Timm Spork: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Timm |ErsterAutorNachname=Spork |FurtherAuthors=Christel Baier; Joost-Pieter Katoen; Sascha Klüppelholz; Jakob Piribauer }} {{Inproceedings |Referiert=1 |Title=Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains |To appear=0 |Year=2025 |Month=Juli |Booktitle=Proceedings of the 37th International Conference on Computer Aided Verification (CAV2025), Part II |Pages=56-81 |Publisher=Springer…“</p> <hr /> <div>{{Publikation Erster Autor<br /> |ErsterAutorVorname=Timm<br /> |ErsterAutorNachname=Spork<br /> |FurtherAuthors=Christel Baier; Joost-Pieter Katoen; Sascha Klüppelholz; Jakob Piribauer<br /> }}<br /> {{Inproceedings<br /> |Referiert=1<br /> |Title=Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains<br /> |To appear=0<br /> |Year=2025<br /> |Month=Juli<br /> |Booktitle=Proceedings of the 37th International Conference on Computer Aided Verification (CAV2025), Part II<br /> |Pages=56-81<br /> |Publisher=Springer<br /> |Editor=Ruzica Piskac, Zvonimir Rakamarić<br /> |Series=Lecture Notes in Computer Science (LNCS)<br /> |Volume=15932<br /> }}<br /> {{Publikation Details<br /> |Abstract=We introduce (ε, δ)-bisimulation, a novel type of approximate probabilistic bisimulation for continuous-time Markov chains. In contrast to related notions, (ε, δ)-bisimulation allows the use of different tolerances for the transition probabilities (ε, additive) and total exit rates (δ, multiplicative) of states. Fundamental properties of the notion, as well as bounds on the absolute difference of time- and reward-bounded reachability probabilities for (ε,δ)-bisimilar states, are established.<br /> |Download=Approximate Probabilistic Bisimulation for CTMC.pdf<br /> |DOI Name=10.1007/978-3-031-98679-6_3<br /> |Projekt=CPEC, CeTI<br /> |Forschungsgruppe=Algebraische und logische Grundlagen der Informatik<br /> }}</div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Datei:Approximate_Probabilistic_Bisimulation_for_CTMC.pdf&diff=43446 2025-10-30T11:53:39Z

<p>Timm Spork: </p> <hr /> <div></div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Inproceedings3621349134&diff=41665 2025-03-05T13:22:09Z

<p>Timm Spork: </p> <hr /> <div>{{Publikation Erster Autor<br /> |ErsterAutorVorname=Timm<br /> |ErsterAutorNachname=Spork<br /> |FurtherAuthors=Christel Baier; Joost-Pieter Katoen; Jakob Piribauer; Tim Quatmann<br /> }}<br /> {{Inproceedings<br /> |Referiert=0<br /> |Title=A Spectrum of Approximate Probabilistic Bisimulations<br /> |To appear=0<br /> |Year=2024<br /> |Month=August<br /> |Booktitle=35th International Conference on Concurrency Theory, CONCUR 2024, September 9-13, 2024, Calgary, Canada<br /> |Pages=37:1--37:19<br /> |Publisher=Schloss Dagstuhl - Leibniz-Zentrum für Informatik<br /> |Editor=Rupak Majumdar and Alexandra Silva<br /> |Series=LIPIcs<br /> |Volume=311<br /> }}<br /> {{Publikation Details<br /> |Abstract=This paper studies various notions of approximate probabilistic bisimulation on labeled Markov chains (LMCs). We introduce approximate versions of weak and branching bisimulation, as well as a notion of ε-perturbed bisimulation that relates LMCs that can be made (exactly) probabilistically bisimilar by small perturbations of their transition probabilities. We explore how the notions interrelate and establish their connections to other well-known notions like ε-bisimulation.<br /> |Download=LIPIcs.CONCUR.2024.37.pdf<br /> |DOI Name=10.4230/LIPICS.CONCUR.2024.37<br /> |Projekt=CPEC, CeTI<br /> |Forschungsgruppe=Verifikation und formale quantitative Analyse<br /> }}</div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Datei:LIPIcs.CONCUR.2024.37.pdf&diff=41664 2025-03-05T13:21:29Z

<p>Timm Spork: </p> <hr /> <div></div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Inproceedings3621349134&diff=41663 2025-03-05T13:19:22Z

<p>Timm Spork: </p> <hr /> <div>{{Publikation Erster Autor<br /> |ErsterAutorVorname=Timm<br /> |ErsterAutorNachname=Spork<br /> |FurtherAuthors=Christel Baier; Joost-Pieter Katoen; Jakob Piribauer; Tim Quatmann<br /> }}<br /> {{Inproceedings<br /> |Referiert=0<br /> |Title=A Spectrum of Approximate Probabilistic Bisimulations<br /> |To appear=0<br /> |Year=2024<br /> |Month=August<br /> |Booktitle=35th International Conference on Concurrency Theory, CONCUR 2024, September 9-13, 2024, Calgary, Canada<br /> |Pages=37:1--37:19<br /> |Publisher=Schloss Dagstuhl - Leibniz-Zentrum für Informatik<br /> |Editor=Rupak Majumdar and Alexandra Silva<br /> |Series=LIPIcs<br /> |Volume=311<br /> }}<br /> {{Publikation Details<br /> |Abstract=This paper studies various notions of approximate probabilistic bisimulation on labeled Markov chains (LMCs). We introduce approximate versions of weak and branching bisimulation, as well as a notion of ε-perturbed bisimulation that relates LMCs that can be made (exactly) probabilistically bisimilar by small perturbations of their transition probabilities. We explore how the notions interrelate and establish their connections to other well-known notions like ε-bisimulation.<br /> |Download=A spectrum of approximate probabilistic bisimulations.pdf<br /> |DOI Name=10.4230/LIPICS.CONCUR.2024.37<br /> |Projekt=CPEC, CeTI<br /> |Forschungsgruppe=Verifikation und formale quantitative Analyse<br /> }}</div>

Timm Spork https://iccl.inf.tu-dresden.de/w/index.php?title=Datei:A_spectrum_of_approximate_probabilistic_bisimulations.pdf&diff=41662 2025-03-05T13:18:35Z

<p>Timm Spork: </p> <hr /> <div></div>

Timm Spork