Minimisation of acyclic deterministic automata in linear time
type: Item
instance of: scholarly article
title: Minimisation of acyclic deterministic automata in linear time
zbMATH Open document ID: 0759.68066
DOI: 10.1016/0304-3975(92)90142-3
author: Dominique Revuz
published in: Theoretical Computer Science
publication date: 1992-09-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 55525
zbMATH Keywords: deterministic automaton
zbMATH Keywords: minimization
zbMATH Keywords: acyclic automata
Wikidata QID: Q56048077
reviewed by: Aleksej Dmitrievich Korshunov
MaRDI profile type: Publication
full work available at URL: 0304-3975(92)90142-3
OpenAlex ID: W2070830131
cites work: On the computational power of pushdown automata
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: Partitioning a graph in \(O(|A|\log_ 2|V|)\)
cites work: Q4091421
cites work: Q5551191
cites work: Q5590814
cites work: Q3239817
cites work: Three Partition Refinement Algorithms
cites work: Q5541339
description: scientific article; zbMATH DE number 55525