Scopul nostru este sprijinirea şi promovarea cercetării ştiinţifice şi facilitarea comunicării între cercetătorii români din întreaga lume.
Staff Login
Premii Ad Astra
Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: http://premii.ad-astra.ro/. Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.
An Incremental Algorithm for Constructing Minimal Deterministic Finite Cover Automata
Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã
Autori: Cezar Câmpeanu, Andrei Paun, Jason R. Smith
Editorial: Theoretical Computer Science, 363(2), p.135-148, 2006.
Rezumat:
We present a fast incremental algorithm for constructing minimal Deterministic Finite Cover Automata (DFCA) for a given language. Since it was shown that the minimal DFCA for a language L has less states than the minimal Deterministic Finite Automata (DFA) for the same language L, this technique seems to be the best choice for incrementally building the automaton for a large language, especially when the number of states in the DFCA is significantly less than the number of states in the corresponding minimal DFA. We have implemented the proposed algorithm and have tested it against the best-known DFCA minimization technique.
Cuvinte cheie: Deterministic Finite Cover Automata (DFCA); DFA; DFCA minimization; Incremental construction