An O(n2) Algorithm for Constructing Minimal Cover Automata for Finite Languages
| Autor: | Andrei Păun, Sheng Yu, Nicolae Sântean |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Nested word Finite-state machine Computer science Powerset construction Timed automaton Pushdown automaton Büchi automaton ω-automaton Automaton Combinatorics Nondeterministic finite automaton with ε-moves TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Deterministic finite automaton DFA minimization Deterministic automaton Probabilistic automaton Automata theory Quantum finite automata Two-way deterministic finite automaton Nondeterministic finite automaton Algorithm Time complexity Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Implementation and Application of Automata ISBN: 9783540424918 CIAA |
| DOI: | 10.1007/3-540-44674-5_20 |
| Popis: | Cover automata were introduced in [1] as an efficient representation of finite languages. In [1], an algorithm was given to transform a DFA that accepts a finite language to a minimal deterministic finite cover automaton (DFCA) with the time complexity O(n4), where n is the number of states of the given DFA. In this paper, we introduce a new efficient transformation algorithm with the time complexity O(n2), which is a significant improvement from the previous algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|