Weak minimization of DFA -- an algorithm and applications

DOI10.1016/j.tcs.2004.07.009zbMath1071.68049OpenAlexW2103119124MaRDI QIDQ703502

G. Eisman, Bala 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• 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\)
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• The Complexity of Enumeration and Reliability Problems
• Minimal NFA Problems are Hard
• An Efficient Formula for Linear Recurrences
• Nonnegative Square Matrices
• A reciprocity theorem for domino tilings
• The combinatorics of cache misses during matrix multiplication

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