2 Search Results for "Lopez, Théodore"

Document
DOI: 10.4230/LIPIcs.CSL.2020.9
A Robust Class of Linear Recurrence Sequences

Authors: Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show that this class is robust by giving several characterisations: polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series, and linear recurrence sequences whose eigenvalues are roots of rational numbers.
Cite as

Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki. A Robust Class of Linear Recurrence Sequences. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barloy_et_al:LIPIcs.CSL.2020.9,
  author =	{Barloy, Corentin and Fijalkow, Nathana\"{e}l and Lhote, Nathan and Mazowiecki, Filip},
  title =	{{A Robust Class of Linear Recurrence Sequences}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.9},
  URN =		{urn:nbn:de:0030-drops-116521},
  doi =		{10.4230/LIPIcs.CSL.2020.9},
  annote =	{Keywords: linear recurrence sequences, weighted automata, cost-register automata}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.75
Determinisation of Finitely-Ambiguous Copyless Cost Register Automata

Authors: Théodore Lopez, Benjamin Monmege, and Jean-Marc Talbot

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

Abstract
Cost register automata (CRA) are machines reading an input word while computing values using write-only registers: values from registers are combined using the two operations, as well as the constants, of a semiring. Particularly interesting is the subclass of copyless CRAs where the content of a register cannot be used twice for updating the registers. Originally deterministic, non-deterministic variant of CRA may also be defined: the semantics is then obtained by combining the values of all accepting runs with the additive operation of the semiring (as for weighted automata). We show that finitely-ambiguous copyless non-deterministic CRAs (i.e. the ones that admit a bounded number of accepting runs on every input word) can be effectively transformed into an equivalent copyless (deterministic) CRA, without requiring any specific property on the semiring. As a corollary, this also shows that regular look-ahead can effectively be removed from copyless CRAs.
Cite as

Théodore Lopez, Benjamin Monmege, and Jean-Marc Talbot. Determinisation of Finitely-Ambiguous Copyless Cost Register Automata. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lopez_et_al:LIPIcs.MFCS.2019.75,
  author =	{Lopez, Th\'{e}odore and Monmege, Benjamin and Talbot, Jean-Marc},
  title =	{{Determinisation of Finitely-Ambiguous Copyless Cost Register Automata}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{75:1--75: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.75},
  URN =		{urn:nbn:de:0030-drops-110190},
  doi =		{10.4230/LIPIcs.MFCS.2019.75},
  annote =	{Keywords: Cost-register automata, Look-ahead removal, Unambiguity, Determinisation}
}
  • Refine by Author
  • 1 Barloy, Corentin
  • 1 Fijalkow, Nathanaël
  • 1 Lhote, Nathan
  • 1 Lopez, Théodore
  • 1 Mazowiecki, Filip
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Quantitative automata

  • Refine by Keyword
  • 1 Cost-register automata
  • 1 Determinisation
  • 1 Look-ahead removal
  • 1 Unambiguity
  • 1 cost-register automata
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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