Search Results

Documents authored by Valero, Pedro


Document
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
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}
}
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