|
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... 6 Jul 2008 16:03
NP with oracle machines Hello, I have a question pertaining to the complexity class NP and oracle machines. Suppose you are dealing with the class NP relative to a particular oracle machine, say one for SAT or TQBF. If you wanted to actually physically compute membership to a language that belongs to this complexity class, what w... 6 Jul 2008 11:57
FCT 2009 conference known? Hi all, Does anyone know where (and maybe when) the next FCT (International Symposium on Fundamentals of Computation Theory) will be held? The 2007 conference site does mention an 'invitation to FCT 2009' but the place is not mentioned. thanks, Johan ... 5 Jul 2008 09:27
How many edges are there in semi cubic digraph How to understand follow digraph: " a simple strong connected digraphs with at most indegree 1 or 2 and outdegree 2 or 1 respectively" (let named it as semi cubic digraph) I think there are at most m=3n/2 edges existance in the semi cubic digraph with n vertecies But a reviewer think that a cycle digrap... 5 Jul 2008 23:44
Question on Sipser example proof I'm a complete newbie to computation theory, so unfortunately my question(s) are likely to seem really naive. This has to do with an example from Sipser's Theory of computation, 2nd Edition, page 24 to 25. It's an inductive proof of loan calculation. He's proving this. P sub t = PM^t - Y(M^t -1/M -1) ... 5 Jul 2008 21:42
Word problems for grammars Hello, i am sorry for asking another pack of questions but sadly I don't know what I should do otherwise to get answers to problems I am stuck on. 1. You can speak of problems (which are always word problems to me) in P and NP without giving any alphabet because it does not matter, i.e. if you formulate a prob... 4 Jul 2008 08:58
Complexity theory Hello, I have a few questions on complexity theory which are perhaps easy to answer for an expert or perhaps at least for a beginner in the field. 1. Is the problem CLIQUE(n) that decides weather an input graph has got an n-clique or not in NP? I suppose it is, because I know that CLIQUE (that gives the maximal... 6 Jul 2008 10:56
Second CALL FOR PAPERS: WfPM'08, September 2008, Timisoara, ROMANIA 2nd CFP: Workshop on Workflow and Process Management (WfPM'08), September 2008, Timisoara, Romania EXTENDED DEADLINES ______________________________________________________________________________________________ WfPM'08 -- Workshop on Workflow and Process Management in conjunction with SYNASC-2008 10th Inte... 2 Jul 2008 16:01
Word problem for boolean expressions On Jul 2, 9:11 am, sanchopanch...(a)web.de wrote: Hello, if you consider the alphabet S={\wedge,\vee.\not,(,),x,0,1} one can think of all boolean expressions B as a language over this alphabet. Is the problem of deciding weather a string s of S* is in B or not in P? My guess is that the easiest way to s... 2 Jul 2008 12:55
Diffused concern for too many papers on PvsNP We know that there are hundreds of people around who think they have solved PvsNP. The history of math is full of similar situations: Open problems attract the attention of many. It seems that on this occasion, I mean PvsNP, there is enormous concern, especially in blogs, regarding the number of naive papers. ... 5 Jul 2008 14:33
VMCAI 2009: Call for Papers =============================================================================== ------------------- CALL FOR PAPERS ------------------- VMCAI 2009 The Tenth International Conference on Verification, Model Checking, and Abstract Interpretation ... 29 Jun 2008 14:12
Connection between reachability and Turing completeness I am currently writing a paper about an analysis that should be feasible for any computational system for which one can decide reachability of configurations, e.g. finite state machines, petri nets etc. This made me wonder: Is there any concise classification of "languages for which reachability is decidable"? I... 30 Jun 2008 17:53 |