Hello, I've been trying to solve the following problem for some time. Let A and B be two languages such that: 0) A and B are in NP 1) there are polynomials p...
... One more thing -- we can assume that there is a language C such that point 2 holds for C and C is in P. This way I try to model a languages from NEXP...
Hi, i am posting this message because the welcome message told me to introduce myself :) I study computer science. I also would like to learn a lot about this...
Hello, I reread the description of the group and noticed, that suggesting books is ok with the list :). Recently I am reading a book by Lane A. Hemaspaandra...
Hi, I am a newcomer as well. I am studying mathematics at Bilkent University, Ankara Turkey. I am interested in this subject especially as a future research...
I have a question related to cryptography? How are Artin Braid groups used in cryptography? I also have a cute question from group theory, which I learn just...
... Any non Abelian group generated by g and h with g^n and h^m as relators? -- Jane - Daria? Come on, the neighbors are starting to talk. Daria - Um... good....
I have following questions related to FSA in Automata Theory. a) an FSA of the language with all words that start or end with double letter. b) an FSA of the...
... I have following questions related to FSA in Automata Theory. a) an FSA of the language with all words that start or end with double letter. b) an FSA of...
... Seems like a trivial application of the pumping lemma. If L was regular, the pumping lemma would apply. Since there can only be one b in the string, there...
This can be proved by simple application of pumping lemma for regular languages If p is the pumping length, consider the string a^pba^3p which belongs to given...
Show proof that the following language over the alphabet {a,b} is not regular using pumping or cutting: L = {a ^i b^n |, n!=0, i=n or i=2n } Thanks, Pete...
Show proof that the following language over the alphabet {a,b} is not regular using pumping or cutting: L = {a ^i b^n |i, n!=0, i=n or i=2n } Thanks, Pete...
... What have you already done about this homework? Show your work and where you're stuck. Hint: consider the previous problem and the fact that regular ...
plzz solve these problems Q1. Consider the language S*, where S = {bb,a}. How many words does this language have of length 4? of length 5? of length 6? What...
plzz solve these problemss of theory of automata Q1. Consider the language S*, where S = {bb,a}. How many words does this language have of length 4? of length...
Hi all, I'm reviewing for my written qualifyings, please tell me if I have made a mistake. Okay to be a regular language it must be expressable by a DFA which ...
L1 = {a^n b^n c^k |n, k=0,1,2,....} The production rules would be as follows: S->WC W -> aWb | epsilon C -> cC | epsilon The trick here is to get the...
Hi, I am studying Theory of Computation and I would like to know about Decidability of Logical Theories. I could read some things in Sipser's book... Is there...
Hi! I'm suggesting a book Computability and Complexity Theory by Homer and Selman. It has a nice introduction about TM's and decidability. ... mais! ...
Hello to all; plz can any one help me in solving following question? plz also see the files section where i upload a question file Q1. Build an FA accepting...
Hello, This email message is a notification to let you know that a file has been uploaded to the Files area of the comp-sci-theory group. File :...
comp-sci-theory@yahoo...
Oct 14, 2003 3:35 pm
1255
hi, there would some one help me understand the padding argument used in analyzing complexity class. what kind of padding function f will be a proper one? ...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
