Polynomial crisp-minimization algorithm for fuzzy deterministic automata
| dc.contributor.author | González de Mendívil Grau, Aitor | |
| dc.contributor.author | Fariña Figueredo, Federico | |
| dc.contributor.author | Stanimirovic, Stefan | |
| dc.contributor.author | Micic, Ivana | |
| dc.contributor.author | González de Mendívil Moreno, José Ramón | |
| dc.contributor.department | Estadística, Informática y Matemáticas | es_ES |
| dc.contributor.department | Estatistika, Informatika eta Matematika | eu |
| dc.contributor.department | Institute of Smart Cities - ISC | en |
| dc.date.accessioned | 2024-11-05T12:13:31Z | |
| dc.date.issued | 2024-11-01 | |
| dc.date.updated | 2024-11-05T12:08:43Z | |
| dc.description.abstract | Designing automata minimization algorithms is a significant topic in Automata Theory and Languages with practical applications. In this paper, we develop an efficient minimization algorithm for deterministic fuzzy finite automata over locally finite lattices. More precisely, the algorithm outputs an equivalent minimal crisp-deterministic fuzzy finite automaton for an input fuzzy deterministic finite automaton (FDfA). The running time of the proposed algorithm is polynomial for particular types of locally finite lattices, specifically for max-min-based complete residuated lattices. The intuition behind the proposed algorithm relies on the polynomial minimization algorithm's intuition for ordinary deterministic automata developed by Vazquez de Parga, Garcia, and Lopez (2013) [35]. The motivation for this study comes from the fact that the original algorithm's notions and meanings are lost in the context of fuzzy automata. Thus, we establish a new theoretical foundation that provides the correctness and the polynomial-time nature of this new crisp-minimization algorithm for FDfAs. | en |
| dc.description.sponsorship | S. Stanimirovic and I. Micic acknowledge the support of the Science Fund of the Republic of Serbia, Grant No. 7750185, Quantitative Automata Models: Fundamental Problems and Applications - QUAM. They are also supported by the Ministry of Science, Technological Development and Innovation, Republic of Serbia, Contract No. 451-03-65/2024-03/200124. | |
| dc.embargo.lift | 2026-11-01 | |
| dc.embargo.terms | 2026-11-01 | |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.citation | González de Mendívil Grau, A., Fariña, F., Stanimirovic, S., Micic, I., González de Mendívil, J. R. (2024). Polynomial crisp-minimization algorithm for fuzzy deterministic automata. Fuzzy Sets and Systems, 495-496, 1-19. https://doi.org/10.1016/j.fss.2024.109108. | |
| dc.identifier.doi | 10.1016/j.fss.2024.109108 | |
| dc.identifier.issn | 0165-0114 | |
| dc.identifier.uri | https://academica-e.unavarra.es/handle/2454/52449 | |
| dc.language.iso | eng | |
| dc.publisher | Elsevier | |
| dc.relation.ispartof | Fuzzy Sets and Systems (2024), vol. 495-496, 109108 | |
| dc.relation.publisherversion | https://doi.org/10.1016/j.fss.2024.109108 | |
| dc.rights | © 2024 Elsevier B.V. This manuscript version is made available under the CC-BY-NC-ND 4.0. | |
| dc.rights.accessRights | info:eu-repo/semantics/embargoedAccess | |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject | Brzozowski's algorithm | en |
| dc.subject | Deterministic fuzzy automaton | en |
| dc.subject | Fuzzy átomaton | en |
| dc.subject | Locally finite lattices | en |
| dc.subject | Minimization algorithm | en |
| dc.title | Polynomial crisp-minimization algorithm for fuzzy deterministic automata | en |
| dc.type | info:eu-repo/semantics/article | |
| dc.type.version | info:eu-repo/semantics/acceptedVersion | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | b5b89afd-b97e-47ff-a168-fe99ad4607b0 | |
| relation.isAuthorOfPublication | 8462737f-e46e-4be7-8741-66da50af6c1d | |
| relation.isAuthorOfPublication | 1c9265d3-e49f-4171-a180-c0450d53173b | |
| relation.isAuthorOfPublication.latestForDiscovery | b5b89afd-b97e-47ff-a168-fe99ad4607b0 |