Theory

Free software JFLAP alternative?
Hi all, can you suggest a software that is similar to JFLAP (www.jflap.org) but which is free (FLOS) software? Thanks for any suggestions. Lou ... 29 Mar 2007 16:44

Efficient algorithm?
Given an unlimited supply of coins of denominations x1; x2; : : : ; xn, we wish to make change for a value v using at most k coins; that is, we wish to find a set of k coins whose total value is v. This might not be possible: for instance, if the denominations are 5 and 10 and k = 6, then we can make change for 55 ... 19 Mar 2007 16:43

CS conference ranking reference at www.conference-ranking.net
Description: Computer science conference ranking reference at www.conference-ranking.net CS Conference Ranking http://www.conference-ranking.net/ Computer_Science_Conference_Ranking.html For the reference of research scientists, this computer science conference ranking (conference-ranking.net) is produced wit... 30 Jan 2007 01:51

A Possible "solution" to the Halting Problem
The Halt program throws an "Invalid Input" exception. This would be analogous to the hardware exception of an attempt to divide by zero. ... 9 Nov 2006 22:08

finding k shortest paths
Is there any other resource on the topic of finding the k shortest paths in digraph than the one publicized by David Eppstein but using the same algorithm? I read the article "http://citeseer.ifi.unizh.ch/cache/papers/cs/12009/http:zSzzSzwww.ics.uci.eduzSz~eppsteinzSzpubszSzEpp-SJC-99.pdf/eppstein97finding.pdf" but... 2 Aug 2006 05:31

Greedy Algorithm
Hello, I was wondering if there is a general proof on proving the optimal solution for making change with the standard Greedy Alogorithm example for change making. I wanted to prove that for any given denomination say C = {8, 4, 2 , 1} for any positive integer n that the greedy algorithm will make change for n usin... 12 Apr 2006 11:00

Complexity Theory for Simpletons
Hi, I am interested in feedback on a paper I wrote here: http://arxiv.org/abs/cs.CC/0507008 entitled "Complexity Theory for Simpletons". It was written for a mathematically-literate audience, although not necessarily mathematicians or computer scientists. First of all, I want to know if readers think the paper is... 31 Mar 2006 10:45

HEAP SORT
Hi, Can somebody please help me understand Heap Sort. How to build a heap and how can I prove that the worst case is nlogn? Thank you for your help. ... 6 Mar 2006 19:47

Software for "Regular Expression" <=> NFA <=> DFA
Hello all, as I'm attending a course that deals heavily with Regular Expressions / DFA / NFA this term and was wondering if there are any software tools out there that support working with these concepts especially converting one into the other. I googled quite a lot but couldn't find anything appropriate. An... 17 May 2005 08:49

Name the thesis: "Formal sentences capture informal ones"
The Church-Turing thesis is familiar to many people, largely because it has been widely discussed both in textbooks and in popular science writing. Having a name helps, too. There is an analogous thesis that is relevant to logic and the foundations of mathematics: (*) Formal sentences (in PA or ZFC for exam... 14 Feb 2005 19:28