notesum.ai

Published at December 6

Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton

cs.FL

F.1.1; F.4.3

Released Date: December 6, 2024

Authors: Günter Rote¹

Aff.: ¹Freie Universität Berlin

Arxiv: http://arxiv.org/pdf/2412.05198v1

Refer to caption

Theorem	$\pi$	$\|\mathcal{M}\|$	$M\in\mathcal{M}$	$f$	acceptance crit.
Thm. 1.1 a	input	4	$7\times 7$ , positive, input	$f=e_{1}$	$>1/7$ or $\geq 1/7$
Thm. 1.1 b	input	6	$7\times 7$ , positive, fixed	$f=e_{1}$	$>1/7$ or $\geq 1/7$
Thm. 1.1 c	input	2	$18\times 18$ , positive, input	$f=e_{1}$	$>1/18$ or $\geq 1/18$
Thm. 1.1 d	input	2	$28\times 28$ , positive, fixed	$f=e_{1}$	$>1/28$ or $\geq 1/28$
Thm. 1.2 a	$\pi=e_{2}$	4	$6\times 6$ , positive, input	$\hskip-16.49995ptf\in[0,1]^{6}$ , input	$>\lambda$ or $\geq\lambda$
Thm. 1.2 b	fixed	5	$6\times 6$ , positive, fixed	$\hskip-16.49995ptf\in[0,1]^{6}$ , input	$>\lambda$ or $\geq\lambda$
Claus [5]	$\pi=e_{2}$	9 (5)	$9\times 9$ , positive, input	$f=e_{1}$	$>1/9$
Claus [5]	$\pi=e_{2}$	2	$65\times 65$ , positive, input	$f=e_{1}$	$>1/65$
	$\pi=e_{2}$	2	( $37\times 37$ ), positive, input	$f=e_{1}$	$>1/37$
B.&C. [1]	$\pi=e_{2}$	2	$46\times 46$ , positive, input	$f=e_{1}$	$>1/46$ or $\geq 1/46$
	$\pi=e_{2}$	2	( $34\times 34$ ), positive, input	$f=e_{1}$	$>1/34$ or $\geq 1/34$
Hirv. [14]	$\pi=e_{2}$	2	$25\times 25$ , positive, input	$f=e_{1}$	$>1/25$
	$\pi=e_{2}$	2	( $20\times 20$ ), positive, input	$f=e_{1}$	$>1/20$