[FRIAM] Abduction

[Marcus Daniels]

"The question I'm now worried about is the facility/frequency with which cyclic graphs can be "simulated" by DAGs (which is why I implied that everywhere we think there might be a convergence to something "real" would require a monotonic parameter)"


Uh, why?  For example, compilation of a recursive function to a control flow graph.


mdaniels at m2:~$ cat t.c
#include <stdbool.h>

int foo(bool flag) {
  if (flag) foo(false);
  else return 0;
}
mdaniels at m2:~$ gcc -fdump-tree-cfg -c t.c
mdaniels at m2:~$ cat t.c.011t.cfg

;; Function foo (foo, funcdef_no=0, decl_uid=1956, cgraph_uid=0, symbol_order=0)

;; 1 loops found
;;
;; Loop 0
;;  header 0, latch 1
;;  depth 0, outer -1
;;  nodes: 0 1 2 3 4 5 6
;; 2 succs { 3 4 }
;; 3 succs { 5 }
;; 4 succs { 6 }
;; 5 succs { 1 }
;; 6 succs { 1 }
foo (_Bool flag)
{
  int D.1962;

  <bb 2> :
  if (flag != 0)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  foo (0);
  goto <bb 5>; [INV]

  <bb 4> :
  D.1962 = 0;
  // predicted unlikely by early return (on trees) predictor.
  goto <bb 6>; [INV]

  <bb 5> :
  return;

  <bb 6> :
<L3>:
  return D.1962;

}



________________________________
From: Friam <friam-bounces at redfish.com> on behalf of uǝlƃ ☣ <gepropella at gmail.com>
Sent: Monday, December 31, 2018 3:05:43 PM
To: FriAM
Subject: Re: [FRIAM] Abduction

Thanks for that paper.  It forced me to remember (and look up) the discussion in Pearl's book ("Causality" 2000) about the Markov assumption and latent structure reduction.  Part of my reaction to John's statement about trying to find a time series that cannot be generated by a sequential machine was a result of Pearl's discussion.  The question I'm now worried about is the facility/frequency with which cyclic graphs can be "simulated" by DAGs (which is why I implied that everywhere we think there might be a convergence to something "real" would require a monotonic parameter).


On 12/31/18 12:35 PM, Frank Wimberly wrote:
> Try this link.  Now I remember that Thomas Richardson first described the
> algorithm and Danks and I implemented it.
>
> http://scholar.google.com/scholar_url?url=https://arxiv.org/pdf/1302.3599&hl=en&sa=X&scisig=AAGBfm23iOsgxDPx5eHVIU1aXYbP1yc_ZA&nossl=1&oi=scholarr


--
☣ uǝlƃ

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
archives back to 2003: http://friam.471366.n2.nabble.com/
FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://redfish.com/pipermail/friam_redfish.com/attachments/20181231/56908bfe/attachment-0001.html>