Category Archives: automata

ALogTime, LogCFL, and threshold circuits: dreams of fast solutions

Our protagonists are the following (DLogTime-) uniform circuit classes NC1 (ALogTime) SAC1 (LogCFL) TC0 (threshold circuits) Interesting things can be said about those classes. Things like Barrington’s theorem (NC1), closure under complementation by inductive counting (SAC1), or circuits for division … Continue reading

Posted in automata | 3 Comments

A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata

A deterministic finite automaton (DFA) is a 5-tuple, , consisting of a finite set of states a finite set of input symbols a (partial) transition function an initial state a set of accept states An isomorphism between two DFAs and … Continue reading

Posted in automata, inverse semigroups, isomorphism, partial functions | 4 Comments

Reversibility of binary relations, substochastic matrices, and partial functions

After the last post, I decided that the next post should contain images. Next I decided that the time to publish another post has come. Here is an image of an acceptor finite-state machine, parsing the string “nice”. How can … Continue reading

Posted in automata, partial functions | Tagged , | 1 Comment