Problem Detail: $L$ is a regular language over the alphabet $Sigma = {a,b}$. The left quotient of $L$ regarding $w in Sigma^*$ is the language $$w^{-1} L := {v mid wv in L}$$ How can I prove that $w^{-1}L$ is regular? Read More …
Author: ignougroup
Does coNP-completeness imply NP-hardness?
Problem Detail: Does coNP-completeness imply NP-hardness? In particular, I have a problem that I have shown to be coNP-complete. Can I claim that it is NP-hard? I realize that I can claim coNP-hardness, but I am not sure if that terminology Read More …
Best problems that are prone to parallelization?
Problem Detail: What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can get speed ups easily. Any other Read More …
CNF Generator for Factoring Problems
Problem Detail: I’ve been reading these: Fast Reduction from RSA to SAT CNF Generator for Factoring Problems (Also have C code implementation) I don’t understand how the reduction from FACT to $3text{-SAT}$ works. Are there any simple articles in which I Read More …
Do undecidable languages exist in constructivist logic?
Problem Detail: Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It’s described on Wikipedia here and here. In particular, the system doesn’t allow for proof by contradiction. I’m wondering, Read More …
How is non-ambuiguity different from determinism?
Problem Detail: I am trying to understand what is meant by “deterministic” in expressions such as “deterministic context-free grammar”. (There are more deterministic “things” in this field). I would appreciate an example more then the most elaborate explanation! If possible. My Read More …
Time units required for Interrupt Cycle
Problem Detail: I am reading William Stallings Computer Organization & Architecture to understand about control unit & micro-operations. Stallings explain that interrupt cycle requires 3 time units to complete : t1 : MBR <- (PC) t2 : MAR <- Save_Address PC Read More …
Hamming Weight to find the sum of 1 bits in the range between A and B inclusive
Problem Detail: I am trying to find the sum of 1 bits in the range between A and B inclusive, where -2^31 <= A <= B <= 2^31 – 1 Input Format: The first line contains the number of test cases Read More …
Howto formally go about proving that two LTL formulas are equivalent?
Problem Detail: Do they need to “unwind” exactly to the same set of paths or does it suffice when one set is contained in the other ? Or is it sufficient to argue that M,s satisfies both LTL formulas for any Read More …
Is the language of TMs that halt on some string recognizable?
Problem Detail: I would like to show that the following language is recognizable: $$L:= { langle M rangle mid M text{ is a TM that halts on some string}}.$$ How do I go about showing that this language is recognizable? I Read More …
