Blogs I Follow

Recent Posts
 ALogTime, LogCFL, and threshold circuits: dreams of fast solutions November 2, 2017
 A subset interpretation (with context morphisms) of the sequent calculus for predicate logic September 24, 2017
 Logic without negation and falsehood December 11, 2016
 Logic without truth September 3, 2016
 Learning category theory: a necessary evil? April 3, 2016
 A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata November 15, 2015
 On Zeros of a Polynomial in a Finite Grid: the AlonFuredi bound September 19, 2015
 Groupoids August 3, 2015
 Reversibility of binary relations, substochastic matrices, and partial functions March 22, 2015
 Algebraic characterizations of inverse semigroups and strongly regular rings December 6, 2014
 Gentzen’s consistency proof is more impressive than you expect December 5, 2013
Recent Comments
 gentzen on ALogTime, LogCFL, and threshold circuits: dreams of fast solutions
 gentzen on ALogTime, LogCFL, and threshold circuits: dreams of fast solutions
 A subset interpretation (with context morphisms) of the sequent calculus for predicate logic  Gentzen translated on Logic without truth
 A subset interpretation (with context morphisms) of the sequent calculus for predicate logic  Gentzen translated on Logic without negation and falsehood
 gentzen on Logic without negation and falsehood
 Paolo Logic on Logic without negation and falsehood
 Logic without negation and falsehood  Gentzen translated on Logic without truth
 vznvzn on Logic without truth
 gentzen on Logic without truth
 vznvzn on Logic without truth
 gentzen on Logic without truth
 Learning category theory: a necessary evil?  Gentzen translated on A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata
 vznvzn on A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata
 gentzen on A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata
 vznvzn on A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata
Author Archives: gentzen
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
2 Comments
A subset interpretation (with context morphisms) of the sequent calculus for predicate logic
The previous two posts used the sequent calculus with a subset interpretation: We work with sequents , and interpret the propositions (and ) as subsets of some universe set . We interpret the sequent itself as . While writing the … Continue reading
Logic without negation and falsehood
In the last post, consideration related to partial functions lead us to present a logic without truth and implication, using the binary minus operation as a dual of implication and substitute for unary negation. But logic without implication and equivalence … Continue reading
Logic without truth
Pi is wrong! But so what? It is neither new, nor complicated enough to count as real math! And suggestions that or might be even better show that it not clearcut either. I recently invested sufficient energy into some logical questions to … Continue reading
Learning category theory: a necessary evil?
The end of my last blog post (about isomorphism testing of reversible deterministic finite automata) explained how category theory gave me the idea that the simplified variant of my question about permutation group isomorphism should be easy to solve: The idea to consider … Continue reading
A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata
A deterministic finite automaton (DFA) is a 5tuple, , 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
On Zeros of a Polynomial in a Finite Grid: the AlonFuredi bound
Originally posted on Anurag's Math Blog:
My joint paper with Aditya Potukuchi, Pete L. Clark and John R. Schmitt is now up on arXiv: arXiv:1508.06020. This work started a few months back when I emailed Pete and John, pointing out an easy generalization…
Posted in Uncategorized
Leave a comment