Given a formal model of the behavior of a system, an objective and some notion of control the goal of controller synthesis is to construct a (finite-state) controller that ensures that the system always satisfies the objective. Often, the controller can base its decisions only on limited observations of the system. This notion of limited observability induces a partial-information game between the controller and the uncontrollable part of the system. A successful controller then realizes an observation-based strategy that enforces the objective. In this thesis we consider the controller synthesis problem in the linear-time setting where the behavior of the system is given as a nondeterministic, labeled transitions system A, where the controller can only partially observe and control the behavior of A. The goal of the thesis is to develop a compositional approach for constructing controllers, suitable to treat conjunctive cascades of linear-time objectives P_1, P_2, ..., P_k in an online manner. We iteratively construct a controller C_1 for system A enforcing P_1, then a controller C_2 enforcing P_2 for the parallel composition of the first controller with the system, and so on. It is crucial for this approach that each controller C_i enforces P_i in a most general manner, being as permissive as possible. Otherwise, behavior that is needed to enforce subsequent objectives could be prematurely removed. Standard notions of strategies and controllers only allow the most general treatment for the limited class of safety objectives. We introduce a novel concept of most general strategies and controllers suited for the compositional treatment of objectives beyond safety. We demonstrate the existence of most general controllers for all enforceable, observation-based omega-regular objectives and provide algorithms for the construction of such most general controllers, with specialized variants for the subclass of safety and co-safety objectives. We furthermore adapt and apply our general framework for the compositional synthesis of most general controllers to the setting of exogenous coordination in the context of the channel-based coordination language Reo and the constraint automata framework and report on our implementation in the verification toolset Vereofy. The construction of most general controllers in Vereofy for omega-regular objectives relies on our tool ltl2dstar for generating deterministic omega-automata from Linear Temporal Logic (LTL) formulas. We introduce a generic improvement for exploiting insensitiveness to stuttering during the determinization construction and evaluate its effectiveness in practice. We further investigate the performance of recently proposed variants of Safra\'s determinization construction in practice.

Given a formal model of the behavior of a system, an objective and some notion of control the goal of controller synthesis is to construct a (finite-state) controller that ensures that the system always satisfies the objective. Often, the controller can base its decisions only on limited observations of the system. This notion of limited observability induces a partial-information game between the controller and the uncontrollable part of the system. A successful controller then realizes an observation-based strategy that enforces the objective. In this thesis we consider the controller synthesis problem in the linear-time setting where the behavior of the system is given as a nondeterministic, labeled transitions system A, where the controller can only partially observe and control the behavior of A. The goal of the thesis is to develop a compositional approach for constructing controllers, suitable to treat conjunctive cascades of linear-time objectives P_1, P_2, ..., P_k in an online manner. We iteratively construct a controller C_1 for system A enforcing P_1, then a controller C_2 enforcing P_2 for the parallel composition of the first controller with the system, and so on. It is crucial for this approach that each controller C_i enforces P_i in a most general manner, being as permissive as possible. Otherwise, behavior that is needed to enforce subsequent objectives could be prematurely removed. Standard notions of strategies and controllers only allow the most general treatment for the limited class of safety objectives. We introduce a novel concept of most general strategies and controllers suited for the compositional treatment of objectives beyond safety. We demonstrate the existence of most general controllers for all enforceable, observation-based omega-regular objectives and provide algorithms for the construction of such most general controllers, with specialized variants for the subclass of safety and co-safety objectives. We furthermore adapt and apply our general framework for the compositional synthesis of most general controllers to the setting of exogenous coordination in the context of the channel-based coordination language Reo and the constraint automata framework and report on our implementation in the verification toolset Vereofy. The construction of most general controllers in Vereofy for omega-regular objectives relies on our tool ltl2dstar for generating deterministic omega-automata from Linear Temporal Logic (LTL) formulas. We introduce a generic improvement for exploiting insensitiveness to stuttering during the determinization construction and evaluate its effectiveness in practice. We further investigate the performance of recently proposed variants of Safra\'s determinization construction in practice.

In this thesis, we investigate different theoretical questions concerning weighted automata models over tree-like input structures. First, we study exact and approximated determinisation and then, we turn to Kleene-like and Büchi-like characterisations. We consider multiple weighted automata models, including weighted tree automata over semirings (Chapters 3 and 4), weighted forest automata over M-monoids (Chapter 5), and rational weighted tree languages with storage (Chapter 6). For an explanation as to why the last class can be considered as a weighted automaton model, we refer to page 188 of the thesis. We will now summarise the main contributions of the thesis. In Chapter 3, we focus on the determinisation of weighted tree automata and present our determinisation framework, called M-sequentialisation, which can model different notions of determinisation from the existing literature. Then, we provide a positive M-sequentialisation result for the case of additively idempotent semirings or finitely M-ambiguous weighted tree automata. Another important contribution of Chapter 3 is Theorem 77, where we provide a blueprint theorem that can be used to find determini- sation results for more classes of semirings and weighted tree automata easily. In fact, instead of repeating an entire determinisation construction, Theorem 77 allows us to prove a determinisation result by finding certain finite equivalence relations. This is a very potent tool for future research in the area of determinisation. In Chapter 4, we move from exact determinisation towards approximate determini- sation. We lift the formalisms and the main results from one approach from the literature from the word case to the tree case. This successfully results in an approximated determinisation construction for weighted tree automata over the tropical semiring. We provide a formal mathematical description of the approximated determinisation construction, rather than an algorithmic description as found in the related approach from the literature. In Chapter 5, we turn away from determinisation and instead consider Kleene-like and Büchi-like characterisations of weighted recognisability. We introduce weighted forest automata over M-monoids, which are a generalisation of weighted tree automata over M-monoids and weighted forest automata over semirings. Then, we prove that our recognisable weighted forest languages can be decomposed into a finite product of recognisable weighted tree languages. We also prove that the initial algebra semantic and the run semantic for weighted forest automata are equivalent under certain conditions. Lastly, we define rational forest expressions and forest M-expressions and and prove that the classes of languages generated by these formalisms coincide with recognisable weighted forest languages under certain conditions. In Chapter 6, we consider rational weighted tree languages with storage, where the storage is introduced by composing rational weighted tree languages without storage with a storage map. It has been proven in the literature that rational weighted tree languages with storage are closed under the rational operations. In Chapter 6, we provide alternative proofs of these closure properties. In fact, we prove that our way of introducing storage to rational weighted tree languages preserves the closure properties from rational weighted tree languages without storage.:1 Introduction 2 Preliminaries 2.1 Languages 2.2 WeightedLanguages 2.3 Weighted Tree Automata 3 A Unifying Framework for the Determinisation of Weighted Tree Automata 3.1 Introduction 3.2 Preliminaries 3.3 Factorisation in Monoids 3.3.1 Ordering Multisets over Monoids 3.3.2 Cayley Graph and Cayley Distance 3.3.3 Divisors and Rests 3.3.4 Factorisation Properties 3.4 Weighted Tree Automata over M_fin(M) and the Twinning Property 3.4.1 Weighted Tree Automata over M_fin(M) 3.4.2 The Twinning Property 3.5 Sequentialisation of Weighted Tree Automata over M_fin(M) 3.5.1 The Sequentialisation Construction 3.5.2 The Finitely R-Ambiguous Case 3.6 Relating WTA over M_fin(M) and WTA over S 3.7 M-Sequentialisation of Weighted Tree Automata 3.7.1 Accumulation of D_B 3.7.2 M-Sequentialisation Results 3.8 Comparison of our Results to the Literature 3.8.1 Determinisation of Unweighted Tree Automata 3.8.2 The Free Monoid Case 3.8.3 The Group Case 3.8.4 The Extremal Case 3.9 Conclusion 4 Approximated Determinisation of Weighted Tree Automata 125 4.1 Introduction 4.2 Preliminaries 4.3 Approximated Determinisation 4.3.1 The Approximated Determinisation Construction 4.3.2 Correctness of the Construction 4.4 The Approximated Twinning Property 4.4.1 Implications for Approximated Determinisability 4.4.2 Decidability of the Twinning Property 4.5 Conclusion 5 Kleene and Büchi Theorems for Weighted Forest Languages over M-Monoids 5.1 Introduction 5.2 Preliminaries 5.3 WeightedForestAutomata 5.3.1 Forests 5.3.2 WeightedForestAutomata 5.3.3 Rectangularity 5.3.4 I-recognisable is R-recognisable 5.4 Kleene’s Theorem 5.4.1 Kleene’s Theorem for Trees 5.4.2 Kleene’s Theorem for Forests 5.4.3 An Inductive Approach 5.5 Büchi’s Theorem 5.5.1 Büchi’s Theorem for Trees 5.5.2 Büchi’s Theorem for Forests 5.6 Conclusion 6 Rational Weighted Tree Languages with Storage 6.1 Introduction 6.2 Preliminaries 6.3 Rational Weighted Tree Languages with Storage 6.4 The Kleene-Goldstine Theorem 6.5 Closure of Rat(S¢,Σ,S) under Rational Operations 6.5.1 Top-Concatenation, Scalar Multiplication, and Sum 6.5.2 α-Concatenation 6.5.3 α-Kleene Star 6.6 Conclusion 7 Outlook References