4 Search Results for "Klimann, Ines"

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.ICALP.2018.131
To Infinity and Beyond

Authors: Ines Klimann

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We prove that if a group generated by a bireversible Mealy automaton contains an element of infinite order, then it must have exponential growth. As a direct consequence, no infinite virtually nilpotent group can be generated by a bireversible Mealy automaton.
Cite as

Ines Klimann. To Infinity and Beyond. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 131:1-131:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{klimann:LIPIcs.ICALP.2018.131,
  author =	{Klimann, Ines},
  title =	{{To Infinity and Beyond}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{131:1--131:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.131},
  URN =		{urn:nbn:de:0030-drops-91359},
  doi =		{10.4230/LIPIcs.ICALP.2018.131},
  annote =	{Keywords: automaton groups, growth of a group, exponential growth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.44
Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups

Authors: Thibault Godin and Ines Klimann

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The simplest example of an infinite Burnside group arises in the class of automaton groups. However there is no known example of such a group generated by a reversible Mealy automaton. It has been proved that, for a connected automaton of size at most 3, or when the automaton is not bireversible, the generated group cannot be Burnside infinite. In this paper, we extend these results to automata with bigger stateset, proving that, if a connected reversible automaton has a prime number of states, it cannot generate an infinite Burnside group.
Cite as

Thibault Godin and Ines Klimann. Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{godin_et_al:LIPIcs.MFCS.2016.44,
  author =	{Godin, Thibault and Klimann, Ines},
  title =	{{Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.44},
  URN =		{urn:nbn:de:0030-drops-64570},
  doi =		{10.4230/LIPIcs.MFCS.2016.44},
  annote =	{Keywords: Burnside problem, automaton groups, reversibility, orbit trees}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.502
The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable

Authors: Ines Klimann

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We prove that a semigroup generated by a reversible two-state Mealy automaton is either finite or free of rank 2. This fact leads to the decidability of finiteness for groups generated by two-state or two-letter invertible-reversible Mealy automata and to the decidability of freeness for semigroups generated by two-state invertible-reversible Mealy automata.
Cite as

Ines Klimann. The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 502-513, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{klimann:LIPIcs.STACS.2013.502,
  author =	{Klimann, Ines},
  title =	{{The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{502--513},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.502},
  URN =		{urn:nbn:de:0030-drops-39605},
  doi =		{10.4230/LIPIcs.STACS.2013.502},
  annote =	{Keywords: Mealy automata, automaton semigroups, decidability of finiteness, decidability of freeness, Nerode equivalence}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018
  • 1 2016
  • 1 2013

  • Refine by Author
  • 3 Klimann, Ines
  • 1 Draghici, Andrei
  • 1 Godin, Thibault
  • 1 Piórkowski, Radosław
  • 1 Ryzhikov, Andrew

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Quantitative automata

  • Refine by Keyword
  • 2 automaton groups
  • 1 Burnside problem
  • 1 Mealy automata
  • 1 Nerode equivalence
  • 1 automaton semigroups
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact