Search Results

Documents authored by Gutiérrez, Elena

Document
DOI: 10.4230/LIPIcs.MFCS.2020.40
A Quasiorder-Based Perspective on Residual Automata

Authors: Pierre Ganty, Elena Gutiérrez, and Pedro Valero

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
In this work, we define a framework of automata constructions based on quasiorders over words to provide new insights on the class of residual automata. We present a new residualization operation and a generalized double-reversal method for building the canonical residual automaton for a given language. Finally, we use our framework to offer a quasiorder-based perspective on NL^*, an online learning algorithm for residual automata. We conclude that quasiorders are fundamental to residual automata as congruences are to deterministic automata.
Cite as

Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A Quasiorder-Based Perspective on Residual Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ganty_et_al:LIPIcs.MFCS.2020.40,
  author =	{Ganty, Pierre and Guti\'{e}rrez, Elena and Valero, Pedro},
  title =	{{A Quasiorder-Based Perspective on Residual Automata}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.40},
  URN =		{urn:nbn:de:0030-drops-127071},
  doi =		{10.4230/LIPIcs.MFCS.2020.40},
  annote =	{Keywords: Residual Automata, Quasiorders, Double-Reversal Method, Canonical RFA, Regular Languages}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.77
A Congruence-based Perspective on Automata Minimization Algorithms

Authors: Pierre Ganty, Elena Gutiérrez, and Pedro Valero

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

Abstract
In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for computing the minimal deterministic automaton of a language.
Cite as

Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A Congruence-based Perspective on Automata Minimization Algorithms. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ganty_et_al:LIPIcs.MFCS.2019.77,
  author =	{Ganty, Pierre and Guti\'{e}rrez, Elena and Valero, Pedro},
  title =	{{A Congruence-based Perspective on Automata Minimization Algorithms}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{77:1--77:14},
  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.77},
  URN =		{urn:nbn:de:0030-drops-110214},
  doi =		{10.4230/LIPIcs.MFCS.2019.77},
  annote =	{Keywords: Double-Reversal Method, Minimization, Automata, Congruences, Regular Languages}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.32
The Parikh Property for Weighted Context-Free Grammars

Authors: Pierre Ganty and Elena Gutiérrez

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Parikh's Theorem states that every context-free grammar (CFG) is equivalent to some regular CFG when the ordering of symbols in the words is ignored. The same is not true for the so-called weighted CFGs, which additionally assign a weight to each grammar rule. If the result holds for a given weighted CFG G, we say that G satisfies the Parikh property. We prove constructively that the Parikh property holds for every weighted nonexpansive CFG. We also give a decision procedure for the property when the weights are over the rationals.
Cite as

Pierre Ganty and Elena Gutiérrez. The Parikh Property for Weighted Context-Free Grammars. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganty_et_al:LIPIcs.FSTTCS.2018.32,
  author =	{Ganty, Pierre and Guti\'{e}rrez, Elena},
  title =	{{The Parikh Property for Weighted Context-Free Grammars}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.32},
  URN =		{urn:nbn:de:0030-drops-99315},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.32},
  annote =	{Keywords: Weighted Context-Free Grammars, Algebraic Language Theory, Parikh Image}
}
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