{"id":{"repo_id":"tu-berlin","oai_identifier":"oai:depositonce.tu-berlin.de:11303/25906"},"canonical_url":"https://search.dev.ndltd.org/etd/tu-berlin/oai:depositonce.tu-berlin.de:11303/25906","repository":{"repo_id":"tu-berlin","name":"Technische Universität Berlin","base_url":"https://api-depositonce.tu-berlin.de/server/oai/request"},"display":{"title":"Learning Mealy machines with local timers","abstract":"Complex real-time systems, including autonomous vehicles, advanced robots, and smart power systems, are set to transform every aspect of daily life. To deploy these systems safely, it is essential to ensure that they behave correctly. However, understanding and verifying their behavior often requires accurate and up-to-date behavioral models, which are not available for many applications. Active automata learning could close this gap, as it enables the automated inference of automaton models through interactions with a black-box system. Yet existing active learning methods for real-time systems often struggle to learn models in reasonable time. This thesis introduces a new method for the efficient active learning of automata from real-time systems. Our method is based on Mealy machines with local timers (MMLTs), a new model class that extends standard Mealy machines with multiple timers. We design MMLTs to be learned efficiently while being sufficiently expressive to model applications from different domains. We present an active learning algorithm for MMLTs and extend it with imprecise symbol filtering, an optimization that leverages fallible prior knowledge of transitions without an effect to reduce runtime. Most critically, our method learns accurate models even if the supplied knowledge is incorrect. We further reduce runtime through two MMLT-specific optimizations for behavioral equivalence testing, a frequent bottleneck in active automata learning. We formally prove the correctness of our method and evaluate its performance across 11 cases studies, ranging from network protocols to automotive systems. Our results show that our method drastically outperforms the state of the art across all models. Furthermore, our optimizations often enable significant runtime reductions. We thereby take active automata learning for real-time systems a significant step closer to an application in practice, and thus help easing the access to up-to-date models for the safe deployment of current and future real-time systems.","abstract_html":"Complex real-time systems, including autonomous vehicles, advanced robots, and smart power systems, are set to transform every aspect of daily life. To deploy these systems safely, it is essential to ensure that they behave correctly. However, understanding and verifying their behavior often requires accurate and up-to-date behavioral models, which are not available for many applications. Active automata learning could close this gap, as it enables the automated inference of automaton models through interactions with a black-box system. Yet existing active learning methods for real-time systems often struggle to learn models in reasonable time. This thesis introduces a new method for the efficient active learning of automata from real-time systems. Our method is based on Mealy machines with local timers (MMLTs), a new model class that extends standard Mealy machines with multiple timers. We design MMLTs to be learned efficiently while being sufficiently expressive to model applications from different domains. We present an active learning algorithm for MMLTs and extend it with imprecise symbol filtering, an optimization that leverages fallible prior knowledge of transitions without an effect to reduce runtime. Most critically, our method learns accurate models even if the supplied knowledge is incorrect. We further reduce runtime through two MMLT-specific optimizations for behavioral equivalence testing, a frequent bottleneck in active automata learning. We formally prove the correctness of our method and evaluate its performance across 11 cases studies, ranging from network protocols to automotive systems. Our results show that our method drastically outperforms the state of the art across all models. Furthermore, our optimizations often enable significant runtime reductions. We thereby take active automata learning for real-time systems a significant step closer to an application in practice, and thus help easing the access to up-to-date models for the safe deployment of current and future real-time systems.","abstract_has_math":false,"creators":["Kogel, Paul Werner"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Glesner, Sabine"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025","date_published":"2025","updated_at":"2026-07-27T21:28:29Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":["https://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.14279/depositonce-24731"],"render_values":[{"text":"https://doi.org/10.14279/depositonce-24731","href":"https://doi.org/10.14279/depositonce-24731","code":true}]}]},"links":{"outbound_url":"https://depositonce.tu-berlin.de/handle/11303/25906","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Glesner, Sabine"]},{"key":"dc:creator","label":"Author","values":["Kogel, Paul Werner"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-11-21T11:18:30Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-11-21T11:18:30Z"]},{"key":"dc:date.issued","label":"Date","values":["2025"]},{"key":"dc:type","label":"Dc Type","values":["Doctoral Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://depositonce.tu-berlin.de/handle/11303/25906","https://doi.org/10.14279/depositonce-24731"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Complex real-time systems, including autonomous vehicles, advanced robots, and smart power systems, are set to transform every aspect of daily life. To deploy these systems safely, it is essential to ensure that they behave correctly. However, understanding and verifying their behavior often requires accurate and up-to-date behavioral models, which are not available for many applications. Active automata learning could close this gap, as it enables the automated inference of automaton models through interactions with a black-box system. Yet existing active learning methods for real-time systems often struggle to learn models in reasonable time. This thesis introduces a new method for the efficient active learning of automata from real-time systems. Our method is based on Mealy machines with local timers (MMLTs), a new model class that extends standard Mealy machines with multiple timers. We design MMLTs to be learned efficiently while being sufficiently expressive to model applications from different domains. We present an active learning algorithm for MMLTs and extend it with imprecise symbol filtering, an optimization that leverages fallible prior knowledge of transitions without an effect to reduce runtime. Most critically, our method learns accurate models even if the supplied knowledge is incorrect. We further reduce runtime through two MMLT-specific optimizations for behavioral equivalence testing, a frequent bottleneck in active automata learning. We formally prove the correctness of our method and evaluate its performance across 11 cases studies, ranging from network protocols to automotive systems. Our results show that our method drastically outperforms the state of the art across all models. Furthermore, our optimizations often enable significant runtime reductions. We thereby take active automata learning for real-time systems a significant step closer to an application in practice, and thus help easing the access to up-to-date models for the safe deployment of current and future real-time systems.","Komplexe Echtzeitsysteme wie autonome Fahrzeuge, fortschrittliche Roboter und intelligente Energiesysteme sind im Begriff, das tägliche Leben grundlegend zu verändern. Um diese Systeme sicher einsetzen zu können, muss ihre korrekte Funktionsweise unbedingt gewährleistet werden. Das erfordert oft präzise Verhaltensmodelle. Für viele Anwendungen sind solche Modelle jedoch nicht verfügbar. Active Automata Learning kann diese Lücke schließen, da es Automatenmodelle durch Interaktion mit einem Black-Box-System lernen kann. Allerdings haben bestehende aktive Lernmethoden für Echtzeitsysteme oft Schwierigkeiten, Modelle in vertretbarer Zeit zu lernen. In dieser Arbeit stellen wir eine neue Methode zum effizienten aktiven Lernen von Automaten für Echtzeitsysteme vor. Unsere Methode basiert auf Mealy machines with local timers (MMLTs), einer neuen Modellklasse, die Mealy Automaten um mehrere Timer erweitert. MMLTs sind speziell dazu entworfen, effizient gelernt werden zu können und gleichzeitig ausreichend mächtig zur Modellierung verschiedener Anwendungen zu sein. Neben MMLTs stellen wir einen aktiven Lernalgorithmus für diese vor und erweitern diesen mit imprecise symbol filtering. Diese Optimierung nutzt Vorwissen über Transitionen ohne Effekt, um die Laufzeit zu reduzieren und lernt selbst mit fehlerhaftem Vorwissen noch korrekte Modelle. Wir stellen außerdem zwei Optimierungen vor, die dazu dienen, das Verhalten von MMLTs effizienter vergleichen und so die Laufzeit weiter zu reduzieren. Wir zeigen die Korrektheit unserer Methode und untersuchen ihre Effizienz anhand von 11 Fallstudien, die von Netzwerkprotokollen bis zu Fahrzeugsystemen reichen. Unsere Ergebnisse zeigen eine erhebliche Effizienzsteigerung gegenüber dem State Of The Art in allen Modellen. Unsere zusätzlichen Optimierungen ermöglichen darüber hinaus oft erhebliche Laufzeitverkürzungen. Wir bringen somit Active Automata Learning einen deutlichen Schritt näher an eine Anwendung in der Praxis und tragen so dazu bei, den Zugang zu präzisen Verhaltensmodellen aktueller und zukünftiger Echtzeitsysteme zu erleichtern."]},{"key":"dc:title","label":"Title","values":["Learning Mealy machines with local timers"]}]}],"canonical_facts":{"dc:contributor.advisor":["Glesner, Sabine"],"dc:creator":["Kogel, Paul Werner"],"dc:date.accessioned":["2025-11-21T11:18:30Z"],"dc:date.available":["2025-11-21T11:18:30Z"],"dc:date.issued":["2025"],"dc:description.abstract":["Complex real-time systems, including autonomous vehicles, advanced robots, and smart power systems, are set to transform every aspect of daily life. To deploy these systems safely, it is essential to ensure that they behave correctly. However, understanding and verifying their behavior often requires accurate and up-to-date behavioral models, which are not available for many applications. Active automata learning could close this gap, as it enables the automated inference of automaton models through interactions with a black-box system. Yet existing active learning methods for real-time systems often struggle to learn models in reasonable time. This thesis introduces a new method for the efficient active learning of automata from real-time systems. Our method is based on Mealy machines with local timers (MMLTs), a new model class that extends standard Mealy machines with multiple timers. We design MMLTs to be learned efficiently while being sufficiently expressive to model applications from different domains. We present an active learning algorithm for MMLTs and extend it with imprecise symbol filtering, an optimization that leverages fallible prior knowledge of transitions without an effect to reduce runtime. Most critically, our method learns accurate models even if the supplied knowledge is incorrect. We further reduce runtime through two MMLT-specific optimizations for behavioral equivalence testing, a frequent bottleneck in active automata learning. We formally prove the correctness of our method and evaluate its performance across 11 cases studies, ranging from network protocols to automotive systems. Our results show that our method drastically outperforms the state of the art across all models. Furthermore, our optimizations often enable significant runtime reductions. We thereby take active automata learning for real-time systems a significant step closer to an application in practice, and thus help easing the access to up-to-date models for the safe deployment of current and future real-time systems.","Komplexe Echtzeitsysteme wie autonome Fahrzeuge, fortschrittliche Roboter und intelligente Energiesysteme sind im Begriff, das tägliche Leben grundlegend zu verändern. Um diese Systeme sicher einsetzen zu können, muss ihre korrekte Funktionsweise unbedingt gewährleistet werden. Das erfordert oft präzise Verhaltensmodelle. Für viele Anwendungen sind solche Modelle jedoch nicht verfügbar. Active Automata Learning kann diese Lücke schließen, da es Automatenmodelle durch Interaktion mit einem Black-Box-System lernen kann. Allerdings haben bestehende aktive Lernmethoden für Echtzeitsysteme oft Schwierigkeiten, Modelle in vertretbarer Zeit zu lernen. In dieser Arbeit stellen wir eine neue Methode zum effizienten aktiven Lernen von Automaten für Echtzeitsysteme vor. Unsere Methode basiert auf Mealy machines with local timers (MMLTs), einer neuen Modellklasse, die Mealy Automaten um mehrere Timer erweitert. MMLTs sind speziell dazu entworfen, effizient gelernt werden zu können und gleichzeitig ausreichend mächtig zur Modellierung verschiedener Anwendungen zu sein. Neben MMLTs stellen wir einen aktiven Lernalgorithmus für diese vor und erweitern diesen mit imprecise symbol filtering. Diese Optimierung nutzt Vorwissen über Transitionen ohne Effekt, um die Laufzeit zu reduzieren und lernt selbst mit fehlerhaftem Vorwissen noch korrekte Modelle. Wir stellen außerdem zwei Optimierungen vor, die dazu dienen, das Verhalten von MMLTs effizienter vergleichen und so die Laufzeit weiter zu reduzieren. Wir zeigen die Korrektheit unserer Methode und untersuchen ihre Effizienz anhand von 11 Fallstudien, die von Netzwerkprotokollen bis zu Fahrzeugsystemen reichen. Unsere Ergebnisse zeigen eine erhebliche Effizienzsteigerung gegenüber dem State Of The Art in allen Modellen. Unsere zusätzlichen Optimierungen ermöglichen darüber hinaus oft erhebliche Laufzeitverkürzungen. Wir bringen somit Active Automata Learning einen deutlichen Schritt näher an eine Anwendung in der Praxis und tragen so dazu bei, den Zugang zu präzisen Verhaltensmodellen aktueller und zukünftiger Echtzeitsysteme zu erleichtern."],"dc:identifier.uri":["https://depositonce.tu-berlin.de/handle/11303/25906","https://doi.org/10.14279/depositonce-24731"],"dc:language.iso":["en"],"dc:rights.uri":["https://creativecommons.org/licenses/by/4.0/"],"dc:title":["Learning Mealy machines with local timers"],"dc:type":["Doctoral Thesis"]},"updated_at":"2026-07-27T21:28:29Z"}