patternMinor
Free description of the Kameda-Weiner algorithm?
Viewed 0 times
thekamedafreeweinerdescriptionalgorithm
Problem
I found the paper "On the State Minimization of Nondeterministic Finite Automata" which, I assume, contains the Kameda-Weiner algorithm that I've been searching for. It's behind a paywall though. I'm just a hobbyist. Can someone explain it, or point me to another source?
Solution
Brzozowski's paper on arXiv might have a full account of the algorithm. He's one of the pioneers in what I've termed the "algebraic approach" for formal language and automata theory - best known for invoking the "Brzozowski derivative" (aka left-quotient) to describe the state transition of a regular language in algebraic terms. It's the same operation that we used in producing a dramatically simpler proof of Parikh's theorem in 1999. For commutative Kleene algebras, the operator actually is a derivative operator complete with its own version of Taylor's Theorem.
In the paper, https://arxiv.org/abs/1301.5585, Brzozowski brings the derivative/quotient infrastructure to bear; but from a casual reading of the paper, I can't tell if he's described the Kameda-Weiner method in full generality or not.
In the paper, https://arxiv.org/abs/1301.5585, Brzozowski brings the derivative/quotient infrastructure to bear; but from a casual reading of the paper, I can't tell if he's described the Kameda-Weiner method in full generality or not.
Context
StackExchange Computer Science Q#13591, answer score: 2
Revisions (0)
No revisions yet.