A congruence-based perspective on automata minimization algorithms

Ganty, Pierre and Gutiérrez Viedma, Elena and Valero Mejía, Pedro (2019). A congruence-based perspective on automata minimization algorithms. In: "44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)", 26-30 Aug 2019, Aachen, Alemania. ISBN 978-3-95977-117-7. pp.. https://doi.org/10.4230/LIPIcs.MFCS.2019.50.

Description

Title: A congruence-based perspective on automata minimization algorithms
Author/s:
  • Ganty, Pierre
  • Gutiérrez Viedma, Elena
  • Valero Mejía, Pedro
Item Type: Presentation at Congress or Conference (Article)
Event Title: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Event Dates: 26-30 Aug 2019
Event Location: Aachen, Alemania
Title of Book: MFCS 2019: 44th International Symposium on Mathematical Foundations of Computer Science
Date: 2019
ISBN: 978-3-95977-117-7
Subjects:
Freetext Keywords: Double-reversal method; Minimization; Automata; Congruences; Regular languages
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Otro
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (553kB) | Preview

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.

Funding Projects

TypeCodeAcronymLeaderTitle
Government of SpainPGC2018-102210-B-I00UnspecifiedFundación IMDEA SoftwareFundamentos para el desarrollo, análisis y comprensión de los blockchains y los contratos inteligentes
Madrid Regional GovernmentS2018/TCS4339BLOQUES-CMUnspecifiedContratos inteligentes y blockchains escalables y seguros mediante verificación y análisis
Government of SpainRYC-2016-20281UnspecifiedFundación IMDEA SoftwareUnspecified
Government of SpainBES-2016-077136UnspecifiedFundación IMDEA SoftwareUnspecified

More information

Item ID: 57611
DC Identifier: http://oa.upm.es/57611/
OAI Identifier: oai:oa.upm.es:57611
DOI: 10.4230/LIPIcs.MFCS.2019.50
Official URL: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=11021
Deposited by: Memoria Investigacion
Deposited on: 17 Feb 2020 10:10
Last Modified: 17 Feb 2020 10:10
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM