Document Open Access Logo

A Quasiorder-Based Perspective on Residual Automata

Authors Pierre Ganty , Elena Gutiérrez , Pedro Valero

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2020.40.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Regular languages
Keywords
  • Residual Automata
  • Quasiorders
  • Double-Reversal Method
  • Canonical RFA
  • Regular Languages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.MFCS.2020.40

Author Details

Pierre Ganty
  • IMDEA Software Institute, Madrid, Spain
Elena Gutiérrez
  • IMDEA Software Institute, Madrid, Spain
  • Universidad Politécnica de Madrid, Spain
Pedro Valero
  • IMDEA Software Institute, Madrid, Spain
  • Universidad Politécnica de Madrid, Spain

Funding

All authors were partially supported by the Spanish project PGC2018-102210-B-I00 BOSCO
  • Ganty, Pierre: Partially supported by the Madrid regional project S2018/TCS-4339 BLOQUES and the Ramón y Cajal fellowship RYC-2016-20281.
  • Gutiérrez, Elena: Partially supported by BES-2016-077136 grant from the Spanish Ministry of Economy, Industry and Competitiveness.

References

  1. Jirí Adámek, Robert S. R. Myers, Henning Urbat, and Stefan Milius. On continuous nondeterminism and state minimality. In MFPS, volume 308 of Electronic Notes in Theoretical Computer Science, pages 3-23. Elsevier, 2014. Google Scholar
  2. Dana Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87-106, 1987. Google Scholar
  3. Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA. In IJCAI, pages 1004-1009, 2009. Google Scholar
  4. Janusz A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata, 12(6):529-561, 1962. Google Scholar
  5. Janusz A. Brzozowski and Hellis Tamm. Theory of átomata. Theor. Comput. Sci., 539:13-27, 2014. Google Scholar
  6. Aldo de Luca and Stefano Varricchio. Well quasi-orders and regular languages. Acta Inf., 31(6):539-557, 1994. Google Scholar
  7. Aldo de Luca and Stefano Varricchio. Finiteness and Regularity in Semigroups and Formal Languages. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 1999. Google Scholar
  8. François Denis, Aurélien Lemay, and Alain Terlutte. Learning regular languages using non deterministic finite automata. In ICGI, volume 1891 of Lecture Notes in Computer Science, pages 39-50. Springer, 2000. Google Scholar
  9. François Denis, Aurélien Lemay, and Alain Terlutte. Residual finite state automata. Fundam. Inform., 51(4):339-368, 2002. Google Scholar
  10. François Denis, Aurélien Lemay, and Alain Terlutte. Learning regular languages using RFSAs. Theor. Comput. Sci., 313(2):267-294, 2004. Google Scholar
  11. Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A congruence-based perspective on automata minimization algorithms. In MFCS, volume 138 of LIPIcs, pages 77:1-77:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  12. Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A quasiorder-based perspective on residual automata, 2020. URL: http://arxiv.org/abs/2007.00359.
  13. Pierre Ganty, Francesco Ranzato, and Pedro Valero. Language inclusion algorithms as complete abstract interpretations. In SAS, volume 11822 of Lecture Notes in Computer Science, pages 140-161. Springer, 2019. Google Scholar
  14. Anna Kasprzik. Inference of residual finite-state tree automata from membership queries and finite positive data. In Developments in Language Theory, volume 6795 of Lecture Notes in Computer Science, pages 476-477. Springer, 2011. Google Scholar
  15. Robert S. R. Myers, Jirí Adámek, Stefan Milius, and Henning Urbat. Coalgebraic constructions of canonical nondeterministic automata. Theor. Comput. Sci., 604:81-101, 2015. Google Scholar
  16. Hellis Tamm. Generalization of the double-reversal method of finding a canonical residual finite state automaton. In DCFS, volume 9118 of Lecture Notes in Computer Science, pages 268-279. Springer, 2015. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact