Theory

Problem with a problem
Hello, take a grammar G with alphabet {0,1} such that (the word problem for) the language L_G={w in (0+1)*|w\in L(G)} is very complex, say in PSPACE or some higher complexity class. Now consider an "easy" problem EASY like: "Is an element of L_G in L_G?". Well, this seems to be fairly easy because the answer ... 10 Jul 2008 13:24

Definition in computation theory
Hello, Is it possible to give a definition of a "partial Turing computable function" as follows? ** start of the "definition" A set X is called "recursive enumerable" if there exists a finite set A (which is called an "alphabet") such that X is a subset of A* (Kleene star) and there is a turing machine T such... 11 Jul 2008 03:48

Turing machine and Stack
Hello, I have a question about equivalence of a turing machine and stack machine where the symbol beneath the stack is read (and removed), the machine changes "states" and can add zero, one or two symbols on top of the stack. Is the stack machine really euqivalent to a turing machine? HOw is it possible to co... 9 Jul 2008 17:50

Complexity table
Hello, I would like to produce a table for the complexity of some problems concerning the "standard" languages (type-0, recursive, type-1, etc.). I consider always the "worst case" which means that I denote the word problem for type-0 languages as "undecidable even if there are some languages of this type which ... 10 Jul 2008 11:20

Grammar for 2^i
Hello, can you imagine a grammar which produces exactly the language {x in {1}* | |x|=2^i, natural number i} which consists of the strings "e,1,11,1111,11111111,..."? Is it possible to give a regular or even a context-free or even a context-sensitive grammar? Thanks, S. ... 10 Jul 2008 20:38

CUDD
Hello, for my research I need to know the number of the assignments, that satisfy the formula. The formula is given by a BDD. Do somebody knows, how I can get this number with the BDD-package CUDD? I thought, it would be possible to calculate this number with the method "FirstNode(.)", but I have two problems ... 8 Jul 2008 06:56

looking for old jounal "Journal of computing systems"
Does anybody know where i can find the "Journal of computing systems" I guess the fist year of publication was 1953 (did I not say it was old) I found a review of articles in it on The Journal of Symbolic Logic, Vol. 19, No. 2 (Jun., 1954), pp. 143-144 Published by: Association for Symbolic Logic http://www.... 22 Jul 2008 14:44

Position: Full Professorship in Mathematical Computer Science at University of Aarhus, Denmark
A full professorship in the area of Mathematical Computer Science is available at the Department of Computer Science (www.daimi.au.dk), starting November 1, 2008. Deadline: August 12, 2008, at 12,00 noon. See full announcement at: http://www.daimi.au.dk/frontpage/open-positions ... 6 Jul 2008 09:54

Position: Full Professorship in Programming Languages and Formal Models at University of Aarhus, Denmark
A full professorship in the area of Programming Languages and Formal Models is available at the Department of Computer Science (www.daimi.au.dk), University of Aarhus, Denmark, starting November 1, 2008. Deadline: August 13, 2008, at 12,00 noon. See full announcement at: http://www.daimi.au.dk/frontpage/ope... 6 Jul 2008 09:54

NEXPTIME...unlimited space?
Hello, I read on the Wikipedia page for NEXPTIME, or NEXP, the following definition for the complexity class: "NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2^p(n)) for some polynomial p(n), and unlimited space." Does... 7 Jul 2008 17:39