Minimisation of Acyclic Deterministic Automata in Linear Time

Abstract We present a linear algorithm for the minimisation of acyclic deterministic automata. This algorithm can be used, in particular, on automaton representing lexicons.

• Publication year

  1992

• Venue

  Theoretical Computer Science

• Publication date

  1992-01-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0304-3975(92)90142-3
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Three Partition Refinement Algorithms

  1987cited by this paper
• Graph-Based Algorithms for Boolean Function Manipulation

  1986cited by this paper
• Compilers: Principles, Techniques, and Tools

  1986cited by this paper
• Partitioning a Graph in O(|A| log2 |V|)

  1982cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• Finite Automata and Their Decision Problems

  1959cited by this paper

• Compiling Quantum Regular Language States

  2026cites this paper
• \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {McDag}$$\end{document}MCDAG: indexing maximal common subseque

  2025cites this paper
• Subsequence-Based Indices for Genome Sequence Analysis

  2025cites this paper
• McDag: Indexing Maximal Common Subsequences in Practice

  2024influential citation
• On the Representation and State Complexity of Block Languages

  2024cites this paper
• Operational State Complexity of Block Languages

  2024cites this paper
• State Complexity of Finite Partial Languages

  2023cites this paper
• Quick Subset Construction

  2023cites this paper
• Efficient Semiring-Weighted Earley Parsing

  2023cites this paper
• Tunnel Parsing with the Token’s Lexeme

  2022cites this paper
• Polynomial time multiplication and normal forms in free bands

  2022cites this paper
• Efficient Weighted Deduction Systems for Earley’s Algorithm Anonymous ACL submission

  2022cites this paper
• Manipulation of Regular Expressions Using Derivatives: An Overview

  2022cites this paper
• Finite-State Text Processing

  2021cites this paper
• Linear-time Minimization of Wheeler DFAs

  2021influential citation
• Extending greedy feature selection algorithms to multiple solutions

  2021influential citation
• Efficient Construction of the Equation Automaton

  2021cites this paper
• Quantum Algorithm for Lexicographically Minimal String Rotation

  2020cites this paper
• Space-Efficient Algorithms for Strings and Prefix-Sortable Graphs

  2020cites this paper
• A unified implementation of automata and expression structures, and of the associated algorithms using enriched categories

  2020influential citation
• Regular Languages meet Prefix Sorting

  2019cites this paper
• Space-Time Pattern Extraction in Alarm Logs for Network Diagnosis

  2019cites this paper
• On Prefix-Sorting Finite Automata

  2019cites this paper
• Scalable Frequent Sequence Mining with Flexible Subsequence Constraints

  2019cites this paper
• Restoring Arabic vowels through omission-tolerant dictionary lookup

  2019cites this paper
• From Tree Automata to String Automata Minimization

  2018cites this paper
• Boosting over Non-deterministic ZDDs

  2018cites this paper
• An Efficient Algorithm for the Construction of the Equation Tree Automaton

  2018cites this paper
• Log Analysis via Space-time Pattern Matching

  2018cites this paper
• Algorithmic Construction and Stochastic Analysis of Optimal Automata for Generalized Strings

  2018cites this paper
• Martin , T . P . , & Azvine , B . ( 2016 ) . An Incremental Fuzzy Approach to Finding

  2017cites this paper
• Many-MADFAct: Concurrently Constructing MADFAs

  2017cites this paper
• An Assessment of Algorithms for Deriving Failure Deterministic Finite Automata

  2017cites this paper
• An assessment of selected algorithms for generating failure deterministic finite automata

  2016cites this paper
• An Incremental Fuzzy Approach to Finding Event Sequences

  2016cites this paper
• Satisfiability via Smooth Pictures

  2016cites this paper
• Efficient Implementation for Deterministic Finite Tree Automata Minimization

  2016cites this paper
• Efficient Deterministic Finite Automata Minimization Based on Backward Depth Information

  2016cites this paper
• Determinization and minimization of finite acyclic automata by incremental techniques

  2016cites this paper
• LZ compression of static linked list tries

  2015cites this paper
• Building Efficient and Compact Data Structures for Simplicial Complexes

  2015cites this paper
• Annotating large lattices with the exact word error

  2015cites this paper
• Representation and Identification of Approximately Similar Event Sequences

  2015cites this paper
• JCLext: A Java Tool for Compiling Finite-State Transducers from Full-Form Lexicons

  2015cites this paper
• Non-Deterministic Finite Cover Automata

  2015cites this paper
• Fast construction of space‐optimized recursive automaton

  2015cites this paper
• A Survey on Operational State Complexity

  2015cites this paper
• Simplifying Nondeterministic Finite Cover Automata

  2014cites this paper
• Cycle-aware minimization of acyclic deterministic finite-state automata

  2014cites this paper
• Minimization of symbolic automata

  2014cites this paper
• An Efficient Algorithm for the Equation Tree Automaton via the k-C-Continuations

  2014influential citation
• Automates codéterministes et automates acycliques : analyse d'algorithmes et génération aléatoire

  2014cites this paper
• Enumeration of minimal acyclic automata via generalized parking functions

  2014cites this paper
• Autour des automates : génération aléatoire et contribution à quelques extensions. (On the subject of automata : random generation and contribution to some extensions)

  2014cites this paper
• A generic finite automata based approach to implementing lymphocyte repertoire models

  2014cites this paper
• A new method to construct a statistical model for Arabic language

  2014cites this paper
• Equivalence of Transducer

  2013cites this paper
• On Generating and Simplifying Decision Trees Using Tree Automata Models

  2013cites this paper
• Computations by fly-automata beyond monadic second-order logic

  2013cites this paper
• Speech Recognition Algorithms Based on Weighted Finite-State Transducers

  2013cites this paper
• Generative Kernels and Score-Spaces for Classi cation of Speech : Progress Report iii

  2012cites this paper
• On-Line Construction of a Small Automaton for a Finite Set of Words

  2012cites this paper
• Habilitation à diriger des recherches

  2012cites this paper
• Sampling different kinds of acyclic automata using Markov chains

  2012cites this paper
• An Efficient Linear Pseudo-minimization Algorithm for Aho-Corasick Automata

  2012influential citation
• Average complexity of Moore's and Hopcroft's algorithms

  2012cites this paper
• Random Generation of Deterministic Acyclic Automata Using Markov Chains

  2011cites this paper
• Average Case Analysis of Moore’s State Minimization Algorithm

  2011cites this paper
• Constructing minimal acyclic deterministic finite automata

  2011cites this paper
• Minimization of Acyclic DFAs

  2011influential citation
• Efficient finite-state algorithms for the application of local grammars

  2011influential citation
• Efficient Eager XPath Filtering over XML Streams

  2011cites this paper
• A Review on State Complexity of Individual Operations

  2011cites this paper
• A New Epsilon Filter for Efficient Composition of Weighted Finite-State Transducers

  2011cites this paper
• Complexity of Operations on Cofinite Languages

  2010influential citation
• A Challenging Family of Automata for Classical Minimization Algorithms

  2010cites this paper
• Synthesis Lectures on Speech and Audio Processing

  2010cites this paper
• Towards the Optimal Minimization of a Pronunciation Dictionary Model

  2010cites this paper
• Efficient and Robust Music Identification With Weighted Finite-State Transducers

  2010cites this paper
• Minimization of Automata

  2010cites this paper
• Circular sturmian words and Hopcroft's algorithm

  2009cites this paper
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 6th International Conference, CPAIOR 2009 Pittsburgh, PA, USA, May 27-31, 2009 Proceedings

  2009cites this paper
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm

  2009cites this paper
• Exact Generation of Acyclic Deterministic Finite Automata

  2009cites this paper
• Longest common subsequence as private search

  2009cites this paper
• General suffix automaton construction algorithm and space bounds

  2009cites this paper
• Reformulating Global Grammar Constraints

  2009cites this paper
• Search Problems for Speech and Audio Sequences

  2009cites this paper
• Weighted Automata Algorithms

  2009cites this paper
• Boosting a Chatterbot Understanding with a Weighted Filtered-Popping Network Parser

  2009cites this paper
• Statistical Language Models within the Algebra of Weighted Rational Languages

  2009cites this paper
• Description and analysis of a bottom-up DFA minimization algorithm

  2008cites this paper
• Speech Recognition with Weighted Finite-State Transducers

  2008cites this paper
• Hopcroft's Algorithm and Cyclic Automata

  2008cites this paper
• Minimizing incomplete automata

  2008cites this paper
• Fast equation automaton computation

  2008cites this paper
• Exact Generation of Acyclic Deterministic Finite

  2008cites this paper
• An automata-theoretic approach to the word problem for omega -terms over R

  2007influential citation
• Morphological annotation of Korean with Directly Maintainable Resources

  2007cites this paper
• Surface realisation: ambiguity and determinism

  2007cites this paper