Skip to main content
5 votes

Automata : Language Containment, Minimality & Graph Homomorphism

For inclusion, using your condition that non-final states can be mapped to final states does not work. Consider for instance that $A$ is a rejecting sink $p_0$, and $B$ is the minimal automaton for ...
Denis's user avatar
  • 8,903
4 votes

Complexity of digraph homomorphism to an oriented cycle

There recently has been some activity in this area. We wrote a program to determine the smallest NP-complete oriented trees, the smallest ones have 20 vertices. More details can be found here https://...
Florian's user avatar
  • 156
4 votes

How do we use directed univalence in directed type theory?

If by UKan you mean the ambient universe of all types in the theory (which is a bit of a misnomer, since there is no real Kan-ness to them), then no, it is not Segal. You should think of UCov as &...
Mike Shulman's user avatar
1 vote

Time complexity of computing homomorphic image

This is true (for all reasonable functions, not just $n\log n$) if $\phi$ is $\epsilon$-free. You do not need to compute $\phi(w)$ explicitly, you just need to simulate a TM $M$ deciding $L$ on $\phi(...
Emil Jeřábek's user avatar
1 vote

Defining functions on non-inductive types using LEM in Coq

I’m not sure I get what you are trying to do – or, rather, how your example corresponds to your goal. Indeed, in your code you postulate those three types a, ...
Meven Lennon-Bertrand's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible