HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Free description of the Kameda-Weiner algorithm?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#13591, answer score: 2

Revisions (0)

No revisions yet.