Weak minimization of DFA -- an algorithm and applications

DOI10.1016/J.TCS.2004.07.009zbMATH Open1071.68049OpenAlexW2103119124MaRDI QIDQ703502FDOQ703502

Authors: G. Eisman, B. Ravikumar 

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.07.009

Recommendations

• Weak Minimization of DFA — An Algorithm and Applications
• Description and analysis of a bottom-up DFA minimization algorithm
• HYPER-MINIMIZATION IN O(n²)
• Hyper-Minimization in O(n 2)
• scientific article; zbMATH DE number 6300100

zbMATH Keywords

DFA minimizationMatrix power formulaTiling automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Enumeration and Reliability Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Minimal NFA Problems are Hard
• Nonnegative Square Matrices
• An Efficient Formula for Linear Recurrences
• A reciprocity theorem for domino tilings
• Domino tilings of rectangles with fixed width
• Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes
• On dimer coverings of rectangles of fixed width
• The problem of kings
• Improved upper bounds for self-avoiding walks in \(\mathbb Z^d\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The combinatorics of cache misses during matrix multiplication

Cited In (3)

• Efficient algorithms for the inference of minimum size DFAs
• Weak Minimization of DFA — An Algorithm and Applications
• Some New Features and Algorithms for the Study of DFA

This page was built for publication: Weak minimization of DFA -- an algorithm and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703502)