You can subscribe to this list here.
2010 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}
(8) 
_{Nov}

_{Dec}


2011 
_{Jan}

_{Feb}

_{Mar}
(5) 
_{Apr}
(4) 
_{May}
(2) 
_{Jun}

_{Jul}
(7) 
_{Aug}
(34) 
_{Sep}
(11) 
_{Oct}
(25) 
_{Nov}
(9) 
_{Dec}
(19) 
2012 
_{Jan}
(3) 
_{Feb}

_{Mar}
(7) 
_{Apr}
(13) 
_{May}
(13) 
_{Jun}
(24) 
_{Jul}
(16) 
_{Aug}
(2) 
_{Sep}

_{Oct}
(14) 
_{Nov}
(34) 
_{Dec}
(9) 
2013 
_{Jan}
(38) 
_{Feb}
(18) 
_{Mar}
(17) 
_{Apr}
(17) 
_{May}
(36) 
_{Jun}
(3) 
_{Jul}
(4) 
_{Aug}
(25) 
_{Sep}
(25) 
_{Oct}
(15) 
_{Nov}
(29) 
_{Dec}
(9) 
2014 
_{Jan}
(40) 
_{Feb}
(84) 
_{Mar}
(25) 
_{Apr}
(47) 
_{May}
(28) 
_{Jun}
(21) 
_{Jul}
(19) 
_{Aug}
(27) 
_{Sep}
(16) 
_{Oct}
(68) 
_{Nov}
(33) 
_{Dec}
(15) 
2015 
_{Jan}
(15) 
_{Feb}
(16) 
_{Mar}
(2) 
_{Apr}
(11) 
_{May}
(16) 
_{Jun}
(65) 
_{Jul}
(26) 
_{Aug}
(22) 
_{Sep}
(18) 
_{Oct}
(4) 
_{Nov}

_{Dec}

S  M  T  W  T  F  S 



1

2
(4) 
3

4
(1) 
5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24
(1) 
25
(2) 
26

27

28
(1) 
29

30




From: Martin <mjb@cs...>  20111128 22:52:51

On Fri, 20111125 at 15:19 0800, Adam Smith wrote: > Here's a linearspace, searchfree encoding based on the idea of > topological sorting: > > > sorted(V) : v(V), sorted(Vi):e(Vi,V). > dag : sorted(V):v(V). > > > Strangely enough, "dag" is not fully computed a groundtime. (Does > anyone have a good reason why not?) My guess would be that it's to do with the conditional literals in the body but I guess Roland would know for sure. > Nonetheless, the solver can evaluate it with one pass of propagation > (zero choices). > > > Devising an ASP solution for the problem of cycle detection in > isolation might sound misguided. But if Alessandro is planning to use > this encoding inside of a larger search process (generating some > artifact for which the presence of cycles is only a side constraint), > then I think it's worth thinking about. Fair; I stand corrected. Cheers,  Martin 
From: Adam Smith <amsmith@so...>  20111125 23:46:23

Here's a linearspace, searchfree encoding based on the idea of topological sorting: sorted(V) : v(V), sorted(Vi):e(Vi,V). dag : sorted(V):v(V). Strangely enough, "dag" is not fully computed a groundtime. (Does anyone have a good reason why not?) Nonetheless, the solver can evaluate it with one pass of propagation (zero choices). Devising an ASP solution for the problem of cycle detection in isolation might sound misguided. But if Alessandro is planning to use this encoding inside of a larger search process (generating some artifact for which the presence of cycles is only a side constraint), then I think it's worth thinking about. On Fri, Nov 25, 2011 at 9:11 AM, Martin <mjb@...> wrote: > On Thu, 20111124 at 14:36 +0100, Alessandro Bruni wrote: > > Hi all, > > I have a problem that I'm trying to solve and is bugging me quite a > > lot: I need to find the presence of cycles in a graph in an efficient > > way, using answer set programming. > > Might you give a little more context on what you mean by 'efficient' and > why you are trying to find one? Finding cycles is a polynomial task so > using an NP problem solving system to solve it is kind of overkill. > > > Let me explain: I have a directed graph of vertices v(1..n) and a > > relation on them e(X,Y) as my input problem. > > I need to find a set of ASP rules that are unsatisfiable iff there is > > no cycle in the relation e(X,Y). > > One solution could be building the transitive closure of e(X,Y) and > > adding constraints that ask for no identity in it: > > > > > > cl(X,Y) : e(X,Y). > > cl(X,Y) : cl(X,Z), cl(Z,Y), X != Z, Z != Y. > > : cl(X,X), v(X). > > > > > > but this would blow up exponentially the number of predicates produced > > by the grounder. > > How do you get exponential? I can only see cubic, maybe quadratic if > you've got some kind of bound on the arity of a node. > > > I know there are algorithms in procedural languages that do this with > > linear time and space complexity, like those used to find strongly > > connected components, so I was wondering if it is possible to build an > > ASP program whose grounding is linear to the size of the graph and is > > able to return unsatisfiable iff there is no cycle in e(X,Y). Or if > > not possible it would be nice to find out a negative result for the > > problem. > > Given you can build a bitwise model of processor instructions I'd be > tempted to conjecture that *any* polynomial algorithm can be converted > into a polynomialy sized problem that is resolvable without search. > However the coefficients would be crazy and it wouldn't actually be > practical. > > Over all I'd suggest using a polynomial procedural algorithm but if you > really want to use ASP then how about: > > > % Every node is either in a cycle or not > 0 { inCycle(N) } 1 : node(N). > > % If a node is in a cycle so must at least one of it's neighbours > : inCycle(N1), 0 { inCycle(N2) : link(N1,N2) } 0. > > % Must have at least one thing in a cycle > : 0 { inCycle(N) : node(N) } 0. > > > It should give a linear number of linear length rules, each answer set > will contain one or more cycles and if there are none then the graph is > a DAG. > > But it's really not a good way of solving this problem. > > HTH > > Cheers, >  Martin > > > > >  > All the data continuously generated in your IT infrastructure > contains a definitive record of customers, application performance, > security threats, fraudulent activity, and more. Splunk takes this > data and makes sense of it. IT sense. And common sense. > http://p.sf.net/sfu/splunknovd2d > _______________________________________________ > Potasscousers mailing list > Potasscousers@... > https://lists.sourceforge.net/lists/listinfo/potasscousers > 
From: Martin <mjb@cs...>  20111125 17:11:13

On Thu, 20111124 at 14:36 +0100, Alessandro Bruni wrote: > Hi all, > I have a problem that I'm trying to solve and is bugging me quite a > lot: I need to find the presence of cycles in a graph in an efficient > way, using answer set programming. Might you give a little more context on what you mean by 'efficient' and why you are trying to find one? Finding cycles is a polynomial task so using an NP problem solving system to solve it is kind of overkill. > Let me explain: I have a directed graph of vertices v(1..n) and a > relation on them e(X,Y) as my input problem. > I need to find a set of ASP rules that are unsatisfiable iff there is > no cycle in the relation e(X,Y). > One solution could be building the transitive closure of e(X,Y) and > adding constraints that ask for no identity in it: > > > cl(X,Y) : e(X,Y). > cl(X,Y) : cl(X,Z), cl(Z,Y), X != Z, Z != Y. > : cl(X,X), v(X). > > > but this would blow up exponentially the number of predicates produced > by the grounder. How do you get exponential? I can only see cubic, maybe quadratic if you've got some kind of bound on the arity of a node. > I know there are algorithms in procedural languages that do this with > linear time and space complexity, like those used to find strongly > connected components, so I was wondering if it is possible to build an > ASP program whose grounding is linear to the size of the graph and is > able to return unsatisfiable iff there is no cycle in e(X,Y). Or if > not possible it would be nice to find out a negative result for the > problem. Given you can build a bitwise model of processor instructions I'd be tempted to conjecture that *any* polynomial algorithm can be converted into a polynomialy sized problem that is resolvable without search. However the coefficients would be crazy and it wouldn't actually be practical. Over all I'd suggest using a polynomial procedural algorithm but if you really want to use ASP then how about: % Every node is either in a cycle or not 0 { inCycle(N) } 1 : node(N). % If a node is in a cycle so must at least one of it's neighbours : inCycle(N1), 0 { inCycle(N2) : link(N1,N2) } 0. % Must have at least one thing in a cycle : 0 { inCycle(N) : node(N) } 0. It should give a linear number of linear length rules, each answer set will contain one or more cycles and if there are none then the graph is a DAG. But it's really not a good way of solving this problem. HTH Cheers,  Martin 
From: Alessandro Bruni <alessandro.bruni@gm...>  20111124 13:36:49

Hi all, I have a problem that I'm trying to solve and is bugging me quite a lot: I need to find the presence of cycles in a graph in an efficient way, using answer set programming. Let me explain: I have a directed graph of vertices v(1..n) and a relation on them e(X,Y) as my input problem. I need to find a set of ASP rules that are unsatisfiable iff there is no cycle in the relation e(X,Y). One solution could be building the transitive closure of e(X,Y) and adding constraints that ask for no identity in it: cl(X,Y) : e(X,Y). cl(X,Y) : cl(X,Z), cl(Z,Y), X != Z, Z != Y. : cl(X,X), v(X). but this would blow up exponentially the number of predicates produced by the grounder. I know there are algorithms in procedural languages that do this with linear time and space complexity, like those used to find strongly connected components, so I was wondering if it is possible to build an ASP program whose grounding is linear to the size of the graph and is able to return unsatisfiable iff there is no cycle in e(X,Y). Or if not possible it would be nice to find out a negative result for the problem. My best regards, Alessandro Bruni 
From: Roland Kaminski <kaminski@cs...>  20111104 14:09:00

On Friday, November 04, 2011 07:57:52 AM Asher Johnson wrote: > I am a student at The University of Texas at Austin and I am currently > taking a class on Programming Languages. My partner and I are working > on adding Answer Set Programming capabilities to Jython. I was looking > to use Gringo as the Grounder and Clasp as the Solver. However, when I > try to compile the current version, I get the following error: Hi Johnson, I CC'ed our mailing list because there might be other users who are interested in this (you might want to subscribe too; it is relatively low traffic). The 3.0.3 version cannot be build as is on MacOS. But I created a set of patches that fix some glitches and allow for compilation on MacOS. You should apply all patches: patch p0 < patch.txt Regards, Roland https://potassco.svn.sourceforge.net/svnroot/potassco/tags/gringo3.0.3/patches/ 
From: Martin <mjb@cs...>  20111102 12:52:23

On Tue, 20111025 at 21:35 +0200, Roland Kaminski wrote: > Hi Adam, just a try to answer some of your questions. I am not sure whether a > logarithmic representation of states makes sense here because you still have > to represent the transition function. Eventually you make all states explicit > again to define state transitions. Maybe there are some special cases where it > is possible to compact the transitions but I do not think this works in > general. I think it depends on whether the transition function can be specified bitwise. This is kind of what the bitblasting encodings are doing, so it can be done, but in restricted cases. More generally you can use the assignment to multiple predicates to represent being in a state; bitwise representations of their number are simply one way of doing this. For example, imagine you have a state machine with state corresponding two a couple of counters and a couple of flags, you could use different literals for the flags and bitwise encodings for the counters so that the machine being in a given state is represented by assignments to all of the variables. If the transition relations don't always involve all of the variables (i.e. 'while the green flag is set, increment the green counter 1 until it reaches the red counter') then you should save something over explicitly representing each state. ... or perhaps I've missed the whole point. I suspect there is some on this in the papers on BlackBox and some of the explicit state and symbolic model checkers (there is another option; use the formulae that describes a set of states rather than trying to represent the states directly). HTH Cheers,  Martin 
From: Michal Certicky <certicky@fm...>  20111102 12:50:11

It really seems to work now. Thanks a lot guys! 2011/11/2 Torsten Grote <Torsten.Grote@...> > On Wednesday 02 November 2011 02:01:00 Michal Certicky wrote: > > Could you please send me the compiled binary? > > I'll send you a precompiled binary for 64bit GNU/Linux later today > offlist. > > Torsten > 
From: Torsten Grote <Torsten.G<rote@un...>  20111102 08:45:44

On Wednesday 02 November 2011 02:01:00 Michal Certicky wrote: > Could you please send me the compiled binary? I'll send you a precompiled binary for 64bit GNU/Linux later today offlist. Torsten 
From: Michal Certicky <certicky@fm...>  20111102 01:01:29

Hi. Hello, your program works with the svn trunk. Nevertheless, aggregates have > to > be treated carefully at the current state of the implementation (in short > they > are buggy under certain circumstances when it comes to incremental > grounding). > So you're saying that the above program that I sent you just works fine with the svn trunk? Could you please send me the compiled binary? (preferably for linux) I would really appreciate it, since getting it to work took too many hours last time (let's just say, I lack any experience with C/C++ & Boost :)). It would help me a great deal. Michal 