Tag Archives: featured

Formalizable Mathematics grant

My proposal Formalizable Mathematics has been recommended for funding by the Simons Foundation for a 2026-2031 Travel Support for Mathematicians grant.

My selected contributions to Mathlib, the library of formalized mathematics for the proof assistant Lean:

Deontic independence challenge

Which of these 128 combinations are satisfiable in Carmo and Jones style deontic logic? (1=true, 0=false) (Here 5(c) is the strong version.)
Some possibilities are ruled out by Observation 5.1.2 that says 5(bcde) imply 5(g); and Lemma II.2.2 that says 5(abcd) imply 5(f), formalized by RJ Reiff.

5(abcdefg) Model
0000000?
0000001?
0000010?
0000011?
0000100?
0000101?
0000110?
0000111?
0001000?
0001001?
0001010?
0001011?
0001100?
0001101?
0001110?
0001111?
0010000?
0010001?
0010010?
0010011?
0010100?
0010101?
0010110?
0010111?
0011000?
0011001?
0011010?
0011011?
0011100?
0011101?
0011110?
0011111?
0100000?
0100001?
0100010?
0100011?
0100100?
0100101?
0100110?
0100111?
0101000?
0101001?
0101010?
0101011?
0101100?
0101101?
0101110?
0101111?
0110000?
0110001?
0110010?
0110011?
0110100?
0110101?
0110110?
0110111?
0111000?
0111001?
0111010?
0111011?
0111100none; Obs. 5.1.2
0111101?
0111110none; Obs. 5.1.2
0111111see: A5_not_implied
1000000?
1000001?
1000010?
1000011?
1000100?
1000101?
1000110?
1000111?
1001000?
1001001?
1001010?
1001011?
1001100?
1001101?
1001110?
1001111?
1010000?
1010001?
1010010?
1010011?
1010100?
1010101?
1010110?
1010111?
1011000?
1011001?
1011010?
1011011?
1011100?
1011101?
1011110?
1011111see: B5_not_implied’
1100000?
1100001?
1100010?
1100011?
1100100?
1100101?
1100110?
1100111?
1101000?
1101001?
1101010?
1101011?
1101100see: C5_not_implied’
1101101?
1101110?
1101111?
1110000?
1110001?
1110010?
1110011?
1110100?
1110101see theorem: strong_do_not_imply_5d_or_5f
1110110?
1110111?
1111000none; see II.2.2
1111001none; see II.2.2
1111010?
1111011see theorem: do_not_imply_5e
1111100 impossible as 5(fg) follow from 5(abcde)
1111101 impossible as 5(fg) follow from 5(abcde)
1111110 impossible as 5(fg) follow from 5(abcde)
1111111 stayAlive, alive, noObligations

Project on Github

A computable measure of irregularity

My book “Automatic complexity: a computable measure of irregularity” was published by de Gruyter on February 19, 2024. It concerns a version of Sipser’s complexity of distinguishing that was introduced by Shallit and Wang in 2001 and has been developed by me and others since 2013. The book’s exercises have formalized solutions in the proof assistant Lean.

Errata

  1. Exercise 1.12: the word “no” should be removed.
  2. Theorem 1.41 (3) refers the reader to Chapter 2 for the function $A_N$. In fact, $A_N$ is introduced in Definition 1.21.
  3. Claim 4.43: $b’\in\Sigma\setminus\{w_1,\dots,w_s\}$ should (obviously) be replaced by $b’\in\Sigma\setminus\{b_1,\dots,b_s\}$.
  4. Theorem 4.49: The text claims Our witnesses for $A^{\mathrm{perm}}(x)\le |x|+1$ are doubly transitive since the generated group is $S_n$. However, the generated group is not $S_n$ in general. A minimal counterexample is the witness for the word $00$, which generates the group $\mathbb Z/3\mathbb Z \ne S_3$. Therefore, whether $A^{\mathrm{tra2}} \le A^{\mathrm{perm}}$ should be considered open. Python calculations suggest it is true for binary words $w$ with $|w|\le 4$, and for 00000, at least.
  5. Theorem 6.6: Two constructions $M_1\times_1 M_2$ and $M_1\times_2 M_2$ are described. The text suggests that $\times_1$ is used for the theorem, but actually $\times_2$ should be used. The operation $\times_1$ can be used to prove the inequality $A_N(x)\le A_N(x\mid y)\cdot A_N(y)$ instead.

The number of languages with maximum state complexity

Lei Liu completed her Master’s degree with the project title Complexity of Options in 2017.
An extension to monotone options (pictured) was presented at
ALH-2018. The new paper is called The number of languages with maximum state complexity and has been accepted for TAMC 2019.

As of 2022, the paper has been through 7 revisions and has been accepted for publication in the journal Algebra Universalis.