Structure function calculator

Null hypothesis: the word was drawn from the uniform distribution $𝑈 𝑛$ of strings of length $𝑛$ .

The $𝑝$ -value at $𝑚$ is the probability that a word drawn from $𝑈 𝑛$ would be accepted by some automaton accepting along at most $2 𝑚$ paths of length $𝑛$ .

Length for randomization:

$𝑝$ -value type	$𝑝$ -value	Subalphabet type	Subalphabet	Structure function point
exact	$𝑑 𝑎 𝑡 𝑢 𝑚 . 𝑚 𝑖 𝑛 𝑝 𝑣 𝑎 𝑙 𝑢 𝑒$	concrete	$𝑑 𝑎 𝑡 𝑢 𝑚 . 𝑎 𝑟 𝑔 𝑚 𝑖 𝑛 𝑝 𝑣 𝑎 𝑙 𝑢 𝑒$	$ℎ * (𝑑 𝑎 𝑡 𝑢 𝑚 . 𝑚 𝑀 𝑖 𝑛 𝑝 𝑉 𝑎 𝑙) = 𝑑 𝑎 𝑡 𝑢 𝑚 . ℎ 𝑀 𝑖 𝑛 𝑝 𝑉 𝑎 𝑙$
estimated	$𝑑 𝑎 𝑡 𝑢 𝑚 . 𝑚 𝑖 𝑛 𝑝 𝑣 𝑎 𝑙 𝑢 𝑒 𝐿 𝑒 𝑛 𝑔 𝑡 ℎ$	abstract	$𝑑 𝑎 𝑡 𝑢 𝑚 . 𝑎 𝑟 𝑔 𝑚 𝑖 𝑛 𝑝 𝑣 𝑎 𝑙 𝑢 𝑒 𝐿 𝑒 𝑛 𝑔 𝑡 ℎ$	$ℎ * (𝑑 𝑎 𝑡 𝑢 𝑚 . 𝑚 𝑀 𝑖 𝑛 𝑝 𝑉 𝑎 𝑙 𝐿 𝑒 𝑛 𝑔 𝑡 ℎ) = 𝑑 𝑎 𝑡 𝑢 𝑚 . ℎ 𝑀 𝑖 𝑛 𝑝 𝑉 𝑎 𝑙 𝐿 𝑒 𝑛 𝑔 𝑡 ℎ$

Bjørn Kjos-Hanssen

Structure function calculator

Professor of Mathematics, University of Hawaii at Manoa