# Tag Info

0

This problem was studied in the following paper. Abdol-Hossein Esfahanian, S.Louis Hakimi, On computing a conditional edge-connectivity of a graph, Information Processing Letters, Volume 27, Issue 4, 1988, Pages 195-199, ISSN 0020-0190, http://dx.doi.org/10.1016/0020-0190(88)90025-7. The idea is identical to Saeed's method, contract pairs of edges and ...

2

I'll try to show this, hope I interpreted the question correctly. Let $A_k=\{0,1\}^k.$ If $f(n)\leq n+\log n$ for $n$ large enough this implies $$\max\{\ell(c(x)):x \in A_1 \cup A_2\cup \ldots \cup A_k \}\leq k+ \log k,$$ for $k\geq N$, for some finite $N$, where $\ell(c(x))$ is the length of the codeword $c(x)$ assigned to $x.$ So this means that  ...

0

Ricardo Poli developed a GP-specific analog of Holland's Schema Theorem: link

5

In Extending Type Theory with Forcing by Guilhem Jaber, Nicolas Tabareau and Matthieu Sozeau, 2012, intuitionistic forcing is presented as an internalization of the presheaf construction, implemented as a type-preserving translation in the style of Bernardy and Lasson's parametricity translation. This means that you can define terms in your usual type ...

10

The first paper by Rabin (1963) gives the basics what you are looking for. The class of languages recognized by probabilistic automata (with cutpoint) is called stochastic languages. Let $P$ be a probabilistic automaton defined on the alphabet $\Sigma$ and $f_P(w)$ be the accepting probability of $P$ on the input $w \in \Sigma^*$. Then, $P$ with ...

5

If you're going to work only in the internal language then you can just use a proof assistant. There is a minor technicality of having or not having powersets, since proof assistants are typically type theories, but Coq's Prop is consistent with an interpretation of Coq in a topos. You're suggesting however to use the machine as a sort of translation tool ...

10

You can check the recent survey by Ambainis and Yakaryilmaz: Automata and Quantum Computing. It is comprehensive and points the essential literature with some open questions. Moreover, here is a list of papers published on quantum automata until 2015.

13

There are two loanable copies at The National Library of Israel. Here is a scanned copy.

Top 50 recent answers are included