Minimisation of acyclic deterministic automata in linear time (Q1190464)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 55525
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Minimisation of acyclic deterministic automata in linear time |
scientific article; zbMATH DE number 55525 |
Statements
Minimisation of acyclic deterministic automata in linear time (English)
0 references
26 September 1992
0 references
A deterministic automaton is acyclic if the underlying graph is acyclic. Two automata are said to be equivalent if and only if they recognise the same language. If \(A\) is an automaton there exists an unique automaton \(M\) minimal by the number of states, recognizing the same language. An automaton with no pair of equivalent states is minimal. The minimal automaton for a given language \(L\) is the unique automaton with the smallest number of states among those recognizing \(L\). The author presents a linear algorithm for the minimization of acyclic automata. This algorithm can be used, in particular, on automaton representing lexicons.
0 references
deterministic automaton
0 references
minimization
0 references
acyclic automata
0 references
0.87852543592453
0 references
0.8207328915596008
0 references
0.8192793130874634
0 references
0.8149402737617493
0 references
0.8091769218444824
0 references
