Weak minimization of DFA -- an algorithm and applications

DOI10.1016/J.TCS.2004.07.009MaRDI QIDQ703502zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

DFA minimizationMatrix power formulaTiling automaton

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• scientific article; zbMATH DE number 1929948 (Why is no real title available?)
• scientific article; zbMATH DE number 1834679 (Why is no real title available?)
• scientific article; zbMATH DE number 3299758 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• A reciprocity theorem for domino tilings
• An Efficient Formula for Linear Recurrences
• Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes
• Domino tilings of rectangles with fixed width
• Improved upper bounds for self-avoiding walks in Z^d
• Matrix multiplication via arithmetic progressions
• Minimal NFA Problems are Hard
• Nonnegative Square Matrices
• On dimer coverings of rectangles of fixed width
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• The Complexity of Enumeration and Reliability Problems
• The combinatorics of cache misses during matrix multiplication
• The problem of kings

Cited in

(3)

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

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)