18 Search Results for "Droste, Manfred"

Document
DOI: 10.4230/DagRep.15.2.89
Semirings in Databases, Automata, and Logic (Dagstuhl Seminar 25081)

Authors: Guillermo Badia, Manfred Droste, Phokion G. Kolaitis, Carles Noguera, Sophie Brinke, Lovro Mrkonjić, and Gaia Petreni

Published in: Dagstuhl Reports, Volume 15, Issue 2 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25081 "Semirings in Databases, Automata, and Logic", which was held from February 16 to 21, 2025. The seminar focused on semirings, a class of algebraic structures with many applications in computer science, particularly in databases and automata. Semirings are used in databases to annotate tuples in the input and output relations of queries (in particular, in the case of bag semantics, using the semiring of natural numbers) allowing to model several relevant aspects of databases. In automata theory, semirings allow to define weighted automata, which have applications in natural language processing, speech recognition, and image compression. Moreover, semirings are strongly related to the algebraic semantics of many-valued logics. The seminar brought together researchers from the communities mentioned above, and it developed a research agenda for studying semirings, guided by a collection of diverse applications. This led to several new collaborations between members from different communities, including joint work for publications.
Cite as

Guillermo Badia, Manfred Droste, Phokion G. Kolaitis, Carles Noguera, Sophie Brinke, Lovro Mrkonjić, and Gaia Petreni. Semirings in Databases, Automata, and Logic (Dagstuhl Seminar 25081). In Dagstuhl Reports, Volume 15, Issue 2, pp. 89-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{badia_et_al:DagRep.15.2.89,
  author =	{Badia, Guillermo and Droste, Manfred and Kolaitis, Phokion G. and Noguera, Carles and Brinke, Sophie and Mrkonji\'{c}, Lovro and Petreni, Gaia},
  title =	{{Semirings in Databases, Automata, and Logic (Dagstuhl Seminar 25081)}},
  pages =	{89--109},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{2},
  editor =	{Badia, Guillermo and Droste, Manfred and Kolaitis, Phokion G. and Noguera, Carles and Brinke, Sophie and Mrkonji\'{c}, Lovro and Petreni, Gaia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.2.89},
  URN =		{urn:nbn:de:0030-drops-230893},
  doi =		{10.4230/DagRep.15.2.89},
  annote =	{Keywords: databases, finite model theory, multi-valued logic, provenance, semirings, weighted automata, weighted logic}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2025.6
Weighted Rewriting: Semiring Semantics for Abstract Reduction Systems

Authors: Emma Ahrens, Jan-Christoph Kassing, Jürgen Giesl, and Joost-Pieter Katoen

Published in: LIPIcs, Volume 337, 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)

Abstract
We present novel semiring semantics for abstract reduction systems (ARSs). More precisely, we provide a weighted version of ARSs, where the reduction steps induce weights from a semiring. Inspired by provenance analysis in database theory and logic, we obtain a formalism that can be used for provenance analysis of arbitrary ARSs. Our semantics handle (possibly unbounded) non-determinism and possibly infinite reductions. Moreover, we develop several techniques to prove upper and lower bounds on the weights resulting from our semantics, and show that in this way one obtains a uniform approach to analyze several different properties like termination, derivational complexity, space complexity, safety, as well as combinations of these properties.
Cite as

Emma Ahrens, Jan-Christoph Kassing, Jürgen Giesl, and Joost-Pieter Katoen. Weighted Rewriting: Semiring Semantics for Abstract Reduction Systems. In 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 337, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahrens_et_al:LIPIcs.FSCD.2025.6,
  author =	{Ahrens, Emma and Kassing, Jan-Christoph and Giesl, J\"{u}rgen and Katoen, Joost-Pieter},
  title =	{{Weighted Rewriting: Semiring Semantics for Abstract Reduction Systems}},
  booktitle =	{10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-374-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{337},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2025.6},
  URN =		{urn:nbn:de:0030-drops-236215},
  doi =		{10.4230/LIPIcs.FSCD.2025.6},
  annote =	{Keywords: Rewriting, Semirings, Semantics, Termination, Verification}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.165
Algebraic Language Theory with Effects

Authors: Fabian Lenke, Stefan Milius, Henning Urbat, and Thorsten Wißmann

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Regular languages - the languages accepted by deterministic finite automata - are known to be precisely the languages recognized by finite monoids. This characterization is the origin of algebraic language theory. In this paper, we generalize the correspondence between automata and monoids to automata with generic computational effects given by a monad, providing the foundations of an effectful algebraic language theory. We show that, under suitable conditions on the monad, a language is computable by an effectful automaton precisely when it is recognizable by (1) an effectful monoid morphism into an effect-free finite monoid, and (2) a monoid morphism into a monad-monoid bialgebra whose carrier is a finitely generated algebra for the monad, the former mode of recognition being conceptually completely new. Our prime application is a novel algebraic approach to languages computed by probabilistic finite automata. Additionally, we derive new algebraic characterizations for nondeterministic probabilistic finite automata and for weighted finite automata over unrestricted semirings, generalizing previous results on weighted algebraic recognition over commutative rings.
Cite as

Fabian Lenke, Stefan Milius, Henning Urbat, and Thorsten Wißmann. Algebraic Language Theory with Effects. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 165:1-165:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lenke_et_al:LIPIcs.ICALP.2025.165,
  author =	{Lenke, Fabian and Milius, Stefan and Urbat, Henning and Wi{\ss}mann, Thorsten},
  title =	{{Algebraic Language Theory with Effects}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{165:1--165:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.165},
  URN =		{urn:nbn:de:0030-drops-235423},
  doi =		{10.4230/LIPIcs.ICALP.2025.165},
  annote =	{Keywords: Automaton, Monoid, Monad, Effect, Algebraic language theory}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.20
Boundedness of Cost Register Automata over the Integer Min-Plus Semiring

Authors: Andrei Draghici, Radosław Piórkowski, and Andrew Ryzhikov

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Cost register automata (CRAs) are deterministic automata with registers taking values from a fixed semiring. A CRA computes a function from words to values from this semiring. CRAs are tightly related to well-studied weighted automata. Given a CRA, the boundedness problem asks if there exists a natural number N such that for every word, the value of the CRA on this word does not exceed N. This problem is known to be undecidable for the class of linear CRAs over the integer min-plus semiring (ℤ∪{+∞}, min, +), but very little is known about its subclasses. In this paper, we study boundedness of copyless linear CRAs with resets over the integer min-plus semiring. We show that it is decidable for such CRAs with at most two registers. More specifically, we show that it is, respectively, NL-complete and in coNP if the numbers in the input are presented in unary and binary. We also provide complexity results for two classes with an arbitrary number of registers. Namely, we show that for CRAs that use the minimum operation only in the output function, boundedness is PSPACE-complete if transferring values to other registers is allowed, and is coNP-complete otherwise. Finally, for each f_i in the hierarchy of fast-growing functions, we provide a stateless CRA with i registers whose output exceeds N only on runs longer than f_i(N). Our construction yields a non-elementary lower bound already for four registers.
Cite as

Andrei Draghici, Radosław Piórkowski, and Andrew Ryzhikov. Boundedness of Cost Register Automata over the Integer Min-Plus Semiring. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{draghici_et_al:LIPIcs.CSL.2025.20,
  author =	{Draghici, Andrei and Pi\'{o}rkowski, Rados{\l}aw and Ryzhikov, Andrew},
  title =	{{Boundedness of Cost Register Automata over the Integer Min-Plus Semiring}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.20},
  URN =		{urn:nbn:de:0030-drops-227775},
  doi =		{10.4230/LIPIcs.CSL.2025.20},
  annote =	{Keywords: cost register automata, boundedness, decidability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.14
Logical Characterizations of Weighted Complexity Classes

Authors: Guillermo Badia, Manfred Droste, Carles Noguera, and Erik Paul

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Fagin’s seminal result characterizing 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 (weighted) models of computations. In this paper, we start the study of descriptive complexity based on weighted Turing machines over arbitrary semirings. We provide machine-independent characterizations (over ordered structures) of the weighted complexity classes NP[𝒮], FP[𝒮], FPLOG[𝒮], FPSPACE[𝒮], and FPSPACE_poly[𝒮] in terms of definability in suitable weighted logics for an arbitrary semiring 𝒮. In particular, we prove weighted versions of Fagin’s theorem (even for arbitrary structures, not necessarily ordered, provided that the semiring is idempotent and commutative), the Immerman-Vardi’s theorem (originally for 𝖯) and the Abiteboul-Vianu-Vardi’s theorem (originally for PSPACE). We also discuss a recent open problem proposed by Eiter and Kiesel. Recently, the above mentioned weighted complexity classes have been investigated in connection to classical counting complexity classes. Furthermore, several classical counting complexity classes have been characterized in terms of particular weighted logics over the semiring ℕ of natural numbers. In this work, we cover several of these classes and obtain new results for others such as NPMV, ⊕𝖯, or the collection of real-valued languages realized by polynomial-time real-valued nondeterministic Turing machines. Furthermore, our results apply to classes based on many other important semirings, such as the max-plus and the min-plus semirings over the natural numbers which correspond to the classical classes MaxP[O(log n)] and MinP[O(log n)], respectively.
Cite as

Guillermo Badia, Manfred Droste, Carles Noguera, and Erik Paul. Logical Characterizations of Weighted Complexity Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{badia_et_al:LIPIcs.MFCS.2024.14,
  author =	{Badia, Guillermo and Droste, Manfred and Noguera, Carles and Paul, Erik},
  title =	{{Logical Characterizations of Weighted Complexity Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.14},
  URN =		{urn:nbn:de:0030-drops-205707},
  doi =		{10.4230/LIPIcs.MFCS.2024.14},
  annote =	{Keywords: Descriptive complexity, Weighted Turing machines, Weighted logics, Semirings}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.44
Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words

Authors: Manfred Droste, Sven Dziadek, and Werner Kuich

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
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. The simple ω-pushdown automata do not use ε-transitions and have a very restricted stack access. In previous work, we could show this automaton model to be expressively equivalent to context-free ω-languages in the unweighted case. Furthermore, semiring-weighted simple ω-pushdown automata recognize all ω-algebraic series. Here, we consider ω-valuation monoids as weight structures. As a first result, we prove that for this weight structure and for simple ω-pushdown automata, Büchi-acceptance and Muller-acceptance are expressively equivalent. In our second result, we derive a Nivat theorem for these automata stating that the behaviors of weighted ω-pushdown automata are precisely the projections of very simple ω-series restricted to ω-context-free languages. The third result is a weighted logic with the same expressive power as the new automaton model. To prove the equivalence, we use a similar result for weighted nested ω-word automata and apply our present result of expressive equivalence of Muller and Büchi acceptance.
Cite as

Manfred Droste, Sven Dziadek, and Werner Kuich. Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{droste_et_al:LIPIcs.FSTTCS.2020.44,
  author =	{Droste, Manfred and Dziadek, Sven and Kuich, Werner},
  title =	{{Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.44},
  URN =		{urn:nbn:de:0030-drops-132850},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.44},
  annote =	{Keywords: Weighted automata, Pushdown automata, Infinite words, Weighted logic}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.38
Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata

Authors: Manfred Droste, Sven Dziadek, and Werner Kuich

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
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 languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Schützenberger 1963). As in the theory of formal grammars, these weighted languages, or omega-algebraic series, can be represented as solutions of mixed omega-algebraic systems of equations and by weighted omega-pushdown automata. In our first main result, we show that mixed omega-algebraic systems can be transformed into Greibach normal form. Our second main result proves that simple omega-reset pushdown automata recognize all omega-algebraic series that are a solution of an omega-algebraic system in Greibach normal form. Simple reset automata do not use epsilon-transitions and can change the stack only by at most one symbol. These results generalize fundamental properties of context-free languages to weighted languages.
Cite as

Manfred Droste, Sven Dziadek, and Werner Kuich. Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{droste_et_al:LIPIcs.FSTTCS.2019.38,
  author =	{Droste, Manfred and Dziadek, Sven and Kuich, Werner},
  title =	{{Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.38},
  URN =		{urn:nbn:de:0030-drops-116003},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.38},
  annote =	{Keywords: Weighted omega-Context-Free Grammars, Algebraic Systems, Greibach Normal Form, Weighted Automata, omega-Pushdown Automata}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.76
Aperiodic Weighted Automata and Weighted First-Order Logic

Authors: Manfred Droste and Paul Gastin

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
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 form a general and widely studied model. We define a suitable notion of a weighted first-order logic. Then we show that this weighted first-order logic and aperiodic polynomially ambiguous weighted automata have the same expressive power. Moreover, we obtain such equivalence results for suitable weighted sublogics and finitely ambiguous or unambiguous aperiodic weighted automata. Our results hold for general weight structures, including all semirings, average computations of costs, bounded lattices, and others.
Cite as

Manfred Droste and Paul Gastin. Aperiodic Weighted Automata and Weighted First-Order Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{droste_et_al:LIPIcs.MFCS.2019.76,
  author =	{Droste, Manfred and Gastin, Paul},
  title =	{{Aperiodic Weighted Automata and Weighted First-Order Logic}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{76:1--76:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.76},
  URN =		{urn:nbn:de:0030-drops-110203},
  doi =		{10.4230/LIPIcs.MFCS.2019.76},
  annote =	{Keywords: Weighted automata, weighted logic, aperiodic automata, first-order logic, unambiguous, finitely ambiguous, polynomially ambiguous}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.76
A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic

Authors: Manfred Droste and Erik Paul

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
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 relational structures can be reduced to the evaluation of sentences in the contributing structures and the index structure. The logic we employ for our weighted extension is based on the weighted MSO logic introduced by Droste and Gastin to obtain a Büchi-type result for weighted automata. We show that for disjoint unions and products of structures, the evaluation of formulas from two respective fragments of the logic can be reduced to the evaluation of formulas in the contributing structures. We also prove that the respective restrictions are necessary. Surprisingly, for the case of disjoint unions, the fragment is the same as the one used in the Büchi-type result of weighted automata. In fact, even the formulas used to show that the respective restrictions are necessary are the same in both cases. However, here proving that they do not allow for a Feferman-Vaught-like decomposition is more complex and employs Ramsey's Theorem. We also show how translation schemes can be applied to go beyond disjoint unions and products.
Cite as

Manfred Droste and Erik Paul. A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{droste_et_al:LIPIcs.MFCS.2018.76,
  author =	{Droste, Manfred and Paul, Erik},
  title =	{{A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{76:1--76:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.76},
  URN =		{urn:nbn:de:0030-drops-96581},
  doi =		{10.4230/LIPIcs.MFCS.2018.76},
  annote =	{Keywords: Quantitative Logic, Quantitative Model Theory, Feferman-Vaught Theorem, Translation Scheme, Transduction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.31
Weighted Operator Precedence Languages

Authors: Manfred Droste, Stefan Dück, Dino Mandrioli, and Matteo Pradella

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
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 the original grammar family, in terms of an automata family (OPA) and an MSO logic; furthermore they significantly generalize the well-known visibly pushdown languages (VPL). In another area of research, quantitative models of systems are also greatly in demand. In this paper, we lay the foundation to marry these two research fields. We introduce weighted operator precedence automata and show how they are both strict extensions of OPA and weighted visibly pushdown automata. We prove a Nivat-like result which shows that quantitative OPL can be described by unweighted OPA and very particular weighted OPA. In a Büchi-like theorem, we show that weighted OPA are expressively equivalent to a weighted MSO-logic for OPL.
Cite as

Manfred Droste, Stefan Dück, Dino Mandrioli, and Matteo Pradella. Weighted Operator Precedence Languages. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{droste_et_al:LIPIcs.MFCS.2017.31,
  author =	{Droste, Manfred and D\"{u}ck, Stefan and Mandrioli, Dino and Pradella, Matteo},
  title =	{{Weighted Operator Precedence Languages}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.31},
  URN =		{urn:nbn:de:0030-drops-81150},
  doi =		{10.4230/LIPIcs.MFCS.2017.31},
  annote =	{Keywords: Quantitative automata, operator precedence languages, input-driven languages, visibly pushdown languages, quantitative logic}
}
Document
DOI: 10.4230/DagRep.4.1.104
Quantitative Models: Expressiveness, Analysis, and New Applications (Dagstuhl Seminar 14041)

Authors: Manfred Droste, Paul Gastin, Kim Gulstrand Larsen, and Axel Legay

Published in: Dagstuhl Reports, Volume 4, Issue 1 (2014)

Abstract
From Jan. 19 to Jan. 24, 2014, "Quantitative Models: Expressiveness, Analysis, and New Applications" was held in Schloss Dagstuhl-Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Manfred Droste, Paul Gastin, Kim Gulstrand Larsen, and Axel Legay. Quantitative Models: Expressiveness, Analysis, and New Applications (Dagstuhl Seminar 14041). In Dagstuhl Reports, Volume 4, Issue 1, pp. 104-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{droste_et_al:DagRep.4.1.104,
  author =	{Droste, Manfred and Gastin, Paul and Larsen, Kim Gulstrand and Legay, Axel},
  title =	{{Quantitative Models: Expressiveness, Analysis, and New Applications (Dagstuhl Seminar 14041)}},
  pages =	{104--124},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{1},
  editor =	{Droste, Manfred and Gastin, Paul and Larsen, Kim Gulstrand and Legay, Axel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.1.104},
  URN =		{urn:nbn:de:0030-drops-45374},
  doi =		{10.4230/DagRep.4.1.104},
  annote =	{Keywords: quantitative models, quantitative analysis, timed and hybrid systems, probabilistic systems, weighted automata, systems biology, smart grid}
}
Document
DOI: 10.4230/DagSemProc.10031.1
10031 Abstracts Collection – Quantitative Models: Expressiveness and Analysis

Authors: Christel Baier, Manfred Droste, Paul Gastin, and Kim Guldstrand Larsen

Published in: Dagstuhl Seminar Proceedings, Volume 10031, Quantitative Models: Expressiveness and Analysis (2010)

Abstract
From Jan 18 to Jan 22, 2010, the Dagstuhl Seminar 10031 ``Quantitative Models: Expressiveness and Analysis '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Christel Baier, Manfred Droste, Paul Gastin, and Kim Guldstrand Larsen. 10031 Abstracts Collection – Quantitative Models: Expressiveness and Analysis. In Quantitative Models: Expressiveness and Analysis. Dagstuhl Seminar Proceedings, Volume 10031, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{baier_et_al:DagSemProc.10031.1,
  author =	{Baier, Christel and Droste, Manfred and Gastin, Paul and Larsen, Kim Guldstrand},
  title =	{{10031 Abstracts Collection – Quantitative Models: Expressiveness and Analysis}},
  booktitle =	{Quantitative Models: Expressiveness and Analysis},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10031},
  editor =	{Christel Baier and Manfred Droste and Paul Gastin and Kim Guldstrand Larsen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10031.1},
  URN =		{urn:nbn:de:0030-drops-26839},
  doi =		{10.4230/DagSemProc.10031.1},
  annote =	{Keywords: Quantitative models, quantitative analysis, timed and hybrid systems, probabilistic systems, weighted automata}
}
Document
DOI: 10.4230/DagSemProc.10031.2
10031 Executive Summary – Quantitative Models: Expressiveness and Analysis

Authors: Christel Baier, Manfred Droste, Paul Gastin, and Kim Guldstrand Larsen

Published in: Dagstuhl Seminar Proceedings, Volume 10031, Quantitative Models: Expressiveness and Analysis (2010)

Abstract
Quantitative models and quantitative analysis in Computer Science are currently intensively studied, resulting in a revision of the foundation of Computer Science where classical yes/no answers are replaced by quantitative analyses. The potential application areas are huge, e.g., performance analysis, operational research or embedded systems. The aim of the seminar was to address three fundamental topics which are closely related: quantitative analysis of real-time and hybrid systems; probabilistic analysis and stochastic automata; weighted automata. These three areas of research have mainly evolved independently so far and the relationship between them has emerged only recently. The seminar brought together leading researchers of the three areas, with the goal of future highly productive cross-fertilizations.
Cite as

Christel Baier, Manfred Droste, Paul Gastin, and Kim Guldstrand Larsen. 10031 Executive Summary – Quantitative Models: Expressiveness and Analysis. In Quantitative Models: Expressiveness and Analysis. Dagstuhl Seminar Proceedings, Volume 10031, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{baier_et_al:DagSemProc.10031.2,
  author =	{Baier, Christel and Droste, Manfred and Gastin, Paul and Larsen, Kim Guldstrand},
  title =	{{10031 Executive Summary – Quantitative Models: Expressiveness and Analysis}},
  booktitle =	{Quantitative Models: Expressiveness and Analysis},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10031},
  editor =	{Christel Baier and Manfred Droste and Paul Gastin and Kim Guldstrand Larsen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10031.2},
  URN =		{urn:nbn:de:0030-drops-26824},
  doi =		{10.4230/DagSemProc.10031.2},
  annote =	{Keywords: Quantitative models, quantitative analysis, timed and hybrid systems, probabilistic systems, weighted automata}
}
Document
DOI: 10.4230/DagSemRep.292
Logic, Algebra, and Formal Verification of Concurrent Systems (Dagstuhl Seminar 00481)

Authors: Volker Diekert, Manfred Droste, Anca Muscholl, and Doron Peled

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Volker Diekert, Manfred Droste, Anca Muscholl, and Doron Peled. Logic, Algebra, and Formal Verification of Concurrent Systems (Dagstuhl Seminar 00481). Dagstuhl Seminar Report 292, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{diekert_et_al:DagSemRep.292,
  author =	{Diekert, Volker and Droste, Manfred and Muscholl, Anca and Peled, Doron},
  title =	{{Logic, Algebra, and Formal Verification of Concurrent Systems (Dagstuhl Seminar 00481)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{292},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.292},
  URN =		{urn:nbn:de:0030-drops-151760},
  doi =		{10.4230/DagSemRep.292},
}
Document
DOI: 10.4230/DagSemRep.209
Domain Theory and Its Applications (Dagstuhl Seminar 98181)

Authors: Stephen Brookes, Manfred Droste, and Michael Mislove

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Stephen Brookes, Manfred Droste, and Michael Mislove. Domain Theory and Its Applications (Dagstuhl Seminar 98181). Dagstuhl Seminar Report 209, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1999)

Copy BibTex To Clipboard

@TechReport{brookes_et_al:DagSemRep.209,
  author =	{Brookes, Stephen and Droste, Manfred and Mislove, Michael},
  title =	{{Domain Theory and Its Applications (Dagstuhl Seminar 98181)}},
  pages =	{1--18},
  ISSN =	{1619-0203},
  year =	{1999},
  type = 	{Dagstuhl Seminar Report},
  number =	{209},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.209},
  URN =		{urn:nbn:de:0030-drops-150951},
  doi =		{10.4230/DagSemRep.209},
}
  • Refine by Type
  • 18 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2024
  • 1 2020
  • 2 2019
  • 1 2018
  • Show More...

  • Refine by Author
  • 15 Droste, Manfred
  • 4 Gastin, Paul
  • 2 Badia, Guillermo
  • 2 Baier, Christel
  • 2 Dziadek, Sven
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs
  • 2 DagRep
  • 5 DagSemRep
  • 2 DagSemProc

  • Refine by Classification
  • 4 Theory of computation → Quantitative automata
  • 3 Theory of computation → Logic
  • 3 Theory of computation → Logic and verification
  • 2 Theory of computation → Automata over infinite objects
  • 2 Theory of computation → Formal languages and automata theory
  • Show More...

  • Refine by Keyword
  • 4 weighted automata
  • 3 probabilistic systems
  • 3 quantitative analysis
  • 3 timed and hybrid systems
  • 2 Quantitative models
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact