Search Results

Documents authored by Dziadek, Sven

Document
DOI: 10.4230/LIPIcs.MFCS.2026.24
Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language

Authors: Antoine Amarilli, Sven Dziadek, and Luc Segoufin

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
For a fixed regular language L, the enumeration of L-infixes is the following task: we are given an input word w = a₁ ⋯ a_n and we must enumerate the infixes of w that belong to L, i.e., the pairs i ≤ j such that a_i ⋯ a_j ∈ L. We are interested in dynamic enumeration of L-infixes, where we must additionally support letter substitution updates on w (e.g., "replace the i-th letter of w by a letter a"). Each update changes the set of infixes to enumerate, and resets the enumeration state. We study for which regular languages L we can perform dynamic enumeration of L-infixes in constant delay (i.e., the next infix is always produced in constant time) and constant additional memory throughout the enumeration, while supporting each update in constant time. We show that, for languages L with a neutral letter, if the language L belongs to the class ZG and is extensible (i.e., if u ∈ L and u is a factor of v then v ∈ L), then dynamic enumeration of L-infixes can be achieved with a simple algorithm that ensures constant-time updates and constant delay, but not constant additional memory. Our main contribution is then to show an algorithm that additionally uses only constant additional memory, and applies to a more general class of semi-extensible ZG languages for which we give several equivalent characterizations. We further discuss whether our results can be generalized to larger language classes and show some (conditional) lower bounds.
Cite as

Antoine Amarilli, Sven Dziadek, and Luc Segoufin. Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.MFCS.2026.24,
  author =	{Amarilli, Antoine and Dziadek, Sven and Segoufin, Luc},
  title =	{{Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.24},
  URN =		{urn:nbn:de:0030-drops-274050},
  doi =		{10.4230/LIPIcs.MFCS.2026.24},
  annote =	{Keywords: regular language, dynamic membership, enumeration, infix, ZG, automata}
}
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}
}
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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact