New answers tagged

2

The conjecture does not hold: Let $L$ be the set of prefixes of $(c^*ac^*b)^*$. Then $L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$. Take the word $\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$. For all $k\in\mathbb N$, we can show that $PF_k(\eta)\not\subseteq L'$, as witnessed by $$u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\...


2

This is pretty much an open problem and subject to active research. There are a few proposals available. Here are some of the latest ones: Brain computation by assemblies of neurons Christos H. Papadimitriou, Santosh S. Vempala, Daniel Mitropolsky, Michael Collins, Wolfgang Maass Proceedings of the National Academy of Sciences Jun 2020, 117 (25) 14464-14472;...


9

EDIT: Added Lemma 2 which covers all cases asked about. Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA. Proof. Here's the ...


Top 50 recent answers are included