Manfred Droste
YOU?
Author Swipe
View article: Fagin's Theorem for Semiring Turing Machines
Fagin's Theorem for Semiring Turing Machines Open
In recent years, quantitative complexity over semirings has been intensively investigated. An important problem in this context is to connect computational complexity with logical expressiveness. In this paper we improve on the model of \e…
View article: Run supports and initial algebra supports of weighted automata
Run supports and initial algebra supports of weighted automata Open
We consider weighted automata over words and over trees where the weight algebras are strong bimonoids, i.e., semirings which may lack distributivity. It is well known that, for each such weighted automaton, its run semantics and its initi…
View article: The generating power of weighted tree automata with initial algebra semantics
The generating power of weighted tree automata with initial algebra semantics Open
We consider the images of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings). These images are subsets of the carrier set of the underlying strong bimonoid. We consider locally finite,…
View article: Logical Characterizations of Weighted Complexity Classes
Logical Characterizations of Weighted Complexity Classes Open
Fagin's seminal result characterizing $\mathsf{NP}$ in terms of existential second-order logic started the fruitful field of descriptive complexity theory. In recent years, there has been much interest in the investigation of quantitative …
View article: Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings Open
We show that there is an effectively given zero-sum-free commutative semiring S, contained as the subsemiring of nonnegative elements in an effectively given commutative ordered ring, for which there are no procedures deciding, given a wei…
View article: Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata
Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata Open
A weighted finite automaton has the finite-image property if the image of the weighted language associated with it is finite. We show two undecidability results concerning the finite-image property of weighted finite automata over semiring…
View article: Weighted operator precedence languages
Weighted operator precedence languages Open
In the last years renewed investigation of operator precedence languages (OPL) led to discover important properties thereof: OPL are closed with respect to all major operations, are characterized, besides by the original grammar family, in…
View article: Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids Open
We consider weighted tree automata over strong bimonoids (for short: wta). A wta $\mathcal{A}$ has the finite-image property if its recognized weighted tree language $[\![\mathcal{A}]\!]$ has finite image; moreover, $\mathcal{A}$ has the p…
View article: Greibach Normal Form for $\omega$-Algebraic Systems and Weighted Simple $\omega$-Pushdown Automata
Greibach Normal Form for $\omega$-Algebraic Systems and Weighted Simple $\omega$-Pushdown Automata Open
In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of $\omega$-context-free langu…
View article: Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words
Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words Open
Recently, weighted ω-pushdown automata have been introduced by Droste, Ésik, Kuich. This new type of automaton has access to a stack and models quantitative aspects of infinite words. Here, we consider a simple version of those automata. T…
View article: Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata
Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata Open
In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of omega-context-free language…
View article: Aperiodic Weighted Automata and Weighted First-Order Logic
Aperiodic Weighted Automata and Weighted First-Order Logic Open
By fundamental results of Schützenberger, McNaughton and Papert from the 1970s, the classes of first-order definable and aperiodic languages coincide. Here, we extend this equivalence to a quantitative setting. For this, weighted automata …
View article: Weighted omega-Restricted One Counter Automata
Weighted omega-Restricted One Counter Automata Open
Let $S$ be a complete star-omega semiring and $\Sigma$ be an alphabet. For a weighted $\omega$-restricted one-counter automaton $\mathcal{C}$ with set of states $\{1, \dots, n\}$, $n \geq 1$, we show that there exists a mixed algebraic sys…
View article: Weighted omega-Restricted One Counter Automata
Weighted omega-Restricted One Counter Automata Open
Let $S$ be a complete star-omega semiring and $\Sigma$ be an alphabet. For a weighted $\omega$-restricted one-counter automaton $\mathcal{C}$ with set of states $\{1, \dots, n\}$, $n \geq 1$, we show that there exists a mixed algebraic sys…
View article: A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic
A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic Open
We prove a weighted Feferman-Vaught decomposition theorem for disjoint unions and products of finite structures. The classical Feferman-Vaught Theorem describes how the evaluation of a first order sentence in a generalized product of relat…
View article: MK-fuzzy Automata and MSO Logics
MK-fuzzy Automata and MSO Logics Open
We introduce MK-fuzzy automata over a bimonoid K which is related to the\nfuzzification of the McCarthy-Kleene logic. Our automata are inspired by, and\nintend to contribute to, practical applications being in development in a\nproject on …
View article: The Triple-Pair Construction for Weighted ω-Pushdown Automata
The Triple-Pair Construction for Weighted ω-Pushdown Automata Open
Let S be a complete star-omega semiring and Sigma be an alphabet. For a\nweighted omega-pushdown automaton P with stateset 1...n, n greater or equal to\n1, we show that there exists a mixed algebraic system over a complete\nsemiring-semimo…