Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"monadic second-order logic"”.
-
Verification of graph programs with monadic second-order logic
… E-conditions are only able to express first-order properties of GP 2 graphs, while M-conditions can only express properties of a non-attributed graph. Hence, there is still no logic that can express monadic second-order properties of GP 2 graphs. Moreover, both E-conditions and M-conditions …
-
Automata Linear Dynamic Logic on Finite Traces
Temporal logics are widely used by the Formal Methods and AI communities. Linear Temporal Logic is a popular temporal logic and is valued for its ease of use as well as its balance between expressiveness and complexity. LTL is equivalent in expressiveness to Monadic First-Order Logic and …
-
Deciding Second-order Logics using Database Evaluation Techniques
… that maps the satisfiability problems of second-order logics, in particular WSnS (weak monadic second-order logic with n successors), S1S (monadic second-order logic with one successor), and of μ-calculus, to the problem of query evaluation of Complex-value Datalog queries. In this …
-
Constrained Graph Layouts: Vertices on the Outer Face and on the Integer Grid
… recognize full and closed outer k-planar graphs Monadic Second-order Logic. For the second type, we consider the problem of transferring a given planar drawing onto the integer grid while perserving the original drawings topology; we also generalize a variant of Cauchy's rigidity theorem for …
-
Weighted Logics and Weighted Simple Automata for Context-Free Languages of Infinite Words
… provided a seminal connection between monadic second-order logic and finite automata for both finite and infinite words. This BET- Theorem has been extended by Lautemann, Schwentick and Thérien to context-free languages by introducing a monadic second-order logic with an additional …
-
Easy instances for model checking
… intimately related to the expressibility of the logical language in question. We investigate the parameterized complexity of queries expressible in monadic second order logic over tree-like structures (structures with bounded tree-width) and first order logic over locally tree-like structures. …
-
Sublinear Time Evaluation of Logically Defined Queries on Databases of Bounded Degree
… We mainly focus on queries definable in first-order logic and monadic second-order logic with counting. For boolean queries, we use the framework of property testing. In property testing, for a property P, the goal is to distinguish inputs that have P from those that are far from having P with …
-
Expressiveness and Decidability of Weighted Automata and Weighted Logics
… regular grammars, regular expressions, and monadic second order (MSO) logic. To increase expressiveness, the fundamental idea underlying finite automata and regular languages was also extended to describe not only languages of strings, or words, but also of infinite words by Büchi and …
-
On modal characterisation theorems over finite structures with applications to graph neural networks
… the bisimulation-invariant fragments for various logics. Famously, a seminal theorem by van Benthem characterises the bisimulation-invariant fragment of first-order logic (FOL) in terms of modal logic. Similarly, Janin and Walukiewicz showed that the bisimulation-invariant fragment of monadic …
-
Synthesis and alternating automata over real time
… specification formalisms such as Metric Temporal Logic. Unfortunately, when interpreted over an infinite dense time domain (such as the reals), alternating timed automata have an undecidable language emptiness problem. In this thesis we consider restrictions on this model that restore the …
-
Probabilistic Logic, Probabilistic Regular Expressions, and Constraint Temporal Logic
… the expressive equivalence of finite automata to monadic second order logic and regular expressions, respectively. These fundamental results enjoy applications in nearly every field of theoretical computer science. Around the same time as Büchi and Kleene, Rabin investigated probabilistic finite …
-
Quantitative Automata and Logic for Pictures and Data Words
Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. This connection goes back to a much …
-
Generalizing graph decompositions
… for all problems expressable in a variant of monadic second-order logic. Moving on from directed graphs, we then provide a meta-answer to the broader question of obtaining tree-width analogues for objects other than simple graphs. We do so introducing the theory of spined categories and …
-
Higher-order model checking with traversals
<p>Higher-order recursion schemes are a powerful model of functional computation that grew out of traditional recursive program schemes and generalisations of grammars. It is common to view recursion schemes as generators of possibly-infinite trees, which Ong showed to have a decidable monadic …
-
From plurals to superplurals: in defence of higher-level plural logic
Plural Logic is an extension of First-Order Logic with plural terms and quantifiers. When its plural terms are interpreted as denoting more than one object at once, Plural Logic is usually taken to be ontologically innocent: plural quantifiers do not require a domain of their own, but range …
-
Automata-based decision procedures for weak arithmetics
… <br>arithmetic. A prominent example is the weak monadic second-order logic <br>of one successor, WS1S for short, which is tightly connected to <br>automata over finite words. Nowadays, automata have also emerged as a <br>tool for effectively mechanizing decision procedures for such logical …
-
Forward looking logics and automata
… between one-way and two-way temporal logics, minimization of automata, and the ability to effectively characterize logics. We investigate whether these properties can be extended to tree languages or word languages over an infinite alphabet.</p> <p>It is known that linear temporal …
-
Automatic techniques for proving correctness of heap-manipulating programs
… verification. This dissertation presents two logic-based automatic software verification systems, namely Strand and Dryad, that help in the task of verification of heap-manipulating programs, which is one of the most complex aspects of modern software that eludes automatic verification. Strand …
-
Establishing a Connection Between Graph Structure, Logic, and Language Theory
… there is growing interest in the applications of logic and formal languages to graph theory, and a significant amount of work in this field has recently been consolidated in the publication of a book by Courcelle and Engelfriet. We investigate the potential applications of logic and formal …
-
Multi-weighted Automata Models and Quantitative Logics
… The present thesis develops multi-weighted MSO-logics on finite, infinite and timed words which are expressively equivalent to multi-weighted automata, and studies decision problems for them. In addition, a Nivat-like theorem for weighted timed automata is proved; this theorem establishes a …