-
Notifications
You must be signed in to change notification settings - Fork 9
/
ernst.bib
11771 lines (11065 loc) · 591 KB
/
ernst.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%%% Publications of Michael D. Ernst
% This file (and pag.bib) is processed by the bibtex2web program. See
% https://homes.cs.washington.edu/~mernst/software/bibtex2web.html
% for an explanation of the fields.
%% Keep in sync with ~/public_html/research/pubs-bytopic-categories,
%% which is used for sorting. Catch-all categories such as "Dynamic
%% analysis", "Static analysis", "Testing", and "Verification" are mostly
%% for papers that don't fit anywhere else. Don't clutter those categories
%% with lots of papers that appear elsewhere.
% category = "Defect prediction",
% category = "Concurrency",
% category = "Distributed systems",
% category = "Dynamic analysis",
% category = "Education",
% category = "Immutability (side effects)",
% category = "Specification inference",
% category = "Miscellaneous",
% category = "Natural language processing",
% category = "Programming language design",
% category = "Refactoring",
% category = "Security",
% category = "Software engineering",
% category = "Speculative analysis",
% category = "Static analysis",
% category = "Synthesis",
% category = "Test generation",
% category = "Testing",
% category = "Theory",
% category = "User interfaces",
% category = "Mobile applications",
% category = "Verification",
% FUTUREcategory = "Databases",
% OLDcategory = "Software engineering",
% OPTcategory = "",
% subcategory = "Slicing",
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1989
%%%
@InProceedings{Ernst89a,
author="Michael D. Ernst",
title="ML typechecking is not efficient",
booktitle="Papers of the MIT ACM Undergraduate Conference",
year=1989,
month=apr,
basefilename = "mltypechecking-mitacmug1989",
nodownloads = 1,
category = "Theory",
csetags = "mernst,mernst-Theory,plse",
summary =
"ML programmers have the intuition that ML's typechecking algorithm runs
in linear time. This paper is an early description of the surprising
result (not due to me) that ML typechecking runs in time much worse
than exponential in the size of its input.",
nonPAG = 1,
}
@MastersThesis{Ernst89,
author = "Michael D. Ernst",
title = "Adequate Models for Recursive Program Schemes",
school = miteecs,
year = 1989,
type = "Bachelors thesis",
address = MITaddr,
month = jun,
abstract =
"This thesis is a pedagogical exposition of adequacy for recursive program
schemes in the monotone frame.
Adequacy relates the operational and denotational meanings of a term; it
states that for any term of base type, the operational and denotational
meanings are identical. Adequacy is typically proved in the continuous
frame. This is a pedagogically questionable step; in order to prove
adequacy (or some other property) of a pair of semantics, it would be
desirable to show the property directly, without introducing superfluous
notions. This difficulty is particularly acute because, in general, not
all monotone functions are continuous.
\par
This thesis attempts to work out the concept of adequacy for a class of
monotone first-order recursive program schemes, using Vuillemin and Manna's
method of ``safe'' computation rules. The attempt is very nearly
successful, but at a crucial point the fact that the scheme-definable
functions are, in fact, continuous as well as monotone must be used.",
basefilename = "rpsmodel-ernst-bsthesis",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/rpsmodel-ernst-bsthesis.pdf PDF",
category = "Theory",
csetags = "mernst,mernst-Theory,plse",
summary =
"This paper is a pedagogical exposition of adequacy for recursive
program schemes in the monotone frame. Adequacy states that for any
term of base type, the operational and denotational meanings are
identical, and it is typically proved in the continuous frame.",
nonPAG = 1,
}
@InProceedings{ErnstF89,
author = "Michael D. Ernst and Bruce E. Flinchbaugh",
title = "Image/map correspondence using curve matching",
OPTpages = "",
booktitle = "AAAI Spring Symposium on Robot Navigation",
year = 1989,
OPTorganization = "",
OPTpublisher = "",
address = "Stanford, CA",
month = Mar # "~28--30,",
note = "Also published as Texas Instruments Technical Report
CSC-SIUL-89-12",
OPTannote = "",
abstract =
"We address the general practical problem of determining correspondences
between maps and terrain images, and focus on a static low altitude
airborne scenario. For this case we consider the approach of partially
matching detected and expected curves in the image plane. Expected
curves are generated from a map, using an estimate of the sensor pose
in three dimensions, and matched with simulated detected curves in an
image. We also outline a method for sensor pose refinement using point
correspondences derived from curve matches as input to a relative
orientation algorithm.",
basefilename = "curvematch-aaai1989",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/curvematch-aaai1989.pdf PDF",
category = "Miscellaneous",
csetags = "mernst,mernst-Artificial-intelligence,plse",
summary =
"Correspondences between a real-world image and a map or terrain model
can assist in navigation. This paper describes a technique to find
such correspondences by focusing only on salient curves (roads, rivers,
ridgelines, etc.) rather than the entire image.",
nonPAG = 1,
}
@Unpublished{Ernst89c,
author = "Michael D. Ernst",
title = "Self-reference in {English}",
year = 1989,
month = may,
OLDnote = "Unpublished manuscript",
note =
"The idea from this unpublished term paper was written up by Boolos without
Ernst's knowledge, to appear as ``Quotational Ambiguity,'' by George
Boolos, in {\em On Quine}, (Paulo Leonardi, ed.), pp.~283--296, Cambridge
University Press, 1995. Boolos called the idea ``Ernst's Paradox'' but
refused Ernst's request for coauthorship.",
basefilename = "self-reference-1989",
nodownloads = 1,
category = "Miscellaneous",
csetags = "mernst,mernst-Miscellaneous,plse",
summary =
"This paper shows that certain types of linguistic paradoxes cannot
themselves be expressed without special linguistic conventions; this
fact has since been dubbed ``Ernst's Paradox''.
This paper is recapitulated by ``Quotational Ambiguity,'' by George
Boolos, in {\em Proceedings of the Conference in Honor of
W. V. O. Quine}, San Marino, May 1990 (edited by Paulo Leonardi).",
nonPAG = 1,
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1990
%%%
@TechReport{AIV7,
author = "Randall Davis and Michael D. Ernst",
title = "Intellectual property in computing: ({H}ow) should software
be protected? {A}n industry perspective",
institution = "MIT Artificial Intelligence Laboratory",
year = 1990,
type = "Video",
number = "AIV-7",
address = "Cambridge, Massachusetts",
month = Oct,
basefilename = "",
abstract =
"The future of the software industry is today being shaped in the
courtroom, with decisions in lawsuits defining the nature of
intellectual property for software. While the views of computer
professionals have at times been heard, the discussion is still being
played out in the courts, argued by lawyers, and framed as
fundamentally a legal question: ``What does the existing law say should
be done?''
\par
An alternative view holds that the issue ought to be discussed by those
in the software industry, and that the crucial question is not what the
current law is, but rather what it ought to be. To begin addressing
this question, MIT sponsored a panel discussion on October 30th, 1990,
with panelists from industry engaging in lively discussion and debate
on a variety of positions.",
alternateAbstract =
"Speakers: Frank Ingari, Vice President, Lotus Development Corp.;
Mitchell Kapor, CEO, On Technology; John Landry, CEO, Agility Systems;
Tom Lemberg, Chief Counsel, Lotus Development Corp.; Randall Davis
(Moderator)",
supersededby = "AIM1369 A videotape",
nonPAG = 1,
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1992
%%%
@TechReport{AIM1369,
author = "Michael D. Ernst",
title = "Intellectual property in computing: ({How}) should software
be protected? {An} industry perspective",
institution = "MIT Artificial Intelligence Laboratory",
type = "Memo",
year = 1992,
number = "AIM-1369",
address = "Cambridge, Massachusetts",
month = may,
abstract =
"Recent legal developments may have a greater impact on the computer
industry than technological ones. Some courts have ruled that copyright
law can protect the ``look and feel'' of user interfaces, and patent
law is increasingly being used to erect formidable barriers around
software. Some analysts say that these developments will enfeeble an
otherwise vibrant software industry, creating monopolies by providing
protection where none is needed or desired. Others argue that the
interpretations aren't new and that they will provide the protection
essential to promote innovation and disclosure.
\par
Who's right? And who's arguing these questions, anyway?
\par
The future of the software industry is today being shaped in the
courtroom. Decisions in lawsuits are defining the nature of
intellectual property for software and hence the character of the
industry. While the views of computer professionals have at times been
heard, the discussion is still being played out in the courts, argued
by lawyers, and framed as fundamentally a legal question: ``What does
the existing law say should be done?''
\par
An alternative view holds that the issue ought to be discussed by those
in the software industry and that the crucial question is not what the
current law is, but rather what it ought to be. The fundamental issue
is what shape and character of the industry would be best for all
concerned. After addressing that we can consider what laws would bring
this about.
\par
To begin addressing this question, the MIT Artificial Intelligence
Laboratory, the Laboratory for Computer Science, and the Center for
Coordination Science are hosting a panel discussion on October
30th. Panelists from industry will speak from their extensive
experience, offering a variety of perspectives on what forms of
protection would best serve both the software industry and society in
general:
\par
John Warnock (CEO and co-founder of Adobe Systems) has faced
interesting and difficult decisions regarding what to keep proprietary
and what to place in the public domain, in an attempt to balance the
strategies of licensing proprietary technology and of providing open
specifications that become widely used.
\par
Frank Ingari (Lotus Development Corp., currently in charge of the
Emerging Markets Business Group) had first-hand experience with a
variety of intellectual property protection questions surrounding 1-2-3
while head of Lotus' PC Spreadsheet Division.
\par
Mitchell Kapor (Chairman, CEO and founder of On Technology, founder of
Lotus Development Corp.) has extensive entrepreneurial experience in
the software industry and has testified before Congress about
appropriate protection for software.
\par
John Landry (Chairman, CEO, and co-founder of Agility Systems and
previously Executive Vice President of Development at Cullinet
Software) has been involved in the creation and development of numerous
software companies and is the Chairman of the ADAPSO computer virus
committee.
\par
Tom Lemberg (Chief Counsel, Lotus Development Corp.) is an expert on
international law and international attitudes toward intellectual
property; he will contribute a perspective on the ramifications for
legal decisions and business practices in the US.
\par
Randall Davis (Moderator; Professor of Management, Professor of
Computer Science, Associate Director of the MIT AI Lab), has served as
panelist in a National Academy of Science workshop on Intellectual
Property and Software, and as the court's expert witness in a software
copyright infringement case.
\par
The panelists will make brief presentations, and ample time will be
provided for audience participation. Some additional questions to be
considered include:
\par How should we balance the interests of established companies, start-ups, and users?
\par How can we motivate innovation and iterative improvement, yet protect investment in
software?
\par Where is the value in software?
\par What should be the bounds on intellectual property? Can (and should) an interface
or language be owned?
\par
The panel will offer information on all sides of this complex issue and
encourage the software community to consider the consequences of
various approaches. The discussion is intended to initiate thought
about what kind of industry makes sense for software and how the legal
system can be used to achieve it.",
basefilename = "ipcolloq-transcript-aim1369",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/ipcolloq-press-release.pdf press release;
https://homes.cs.washington.edu/~mernst/pubs/ipcolloq-transcript-aim1369.pdf PDF",
category = "Miscellaneous",
csetags = "mernst,mernst-Miscellaneous,plse",
summary =
{This was the first colloquium on intellectual property in computing to
bring the debate to the technical and social realm; previous analyses
had been from a narrow legal perspective. Computer industry executives
discussed how "look and feel" user interface copyrights and software
patents could affect the industry.},
nonPAG = 1,
}
%%%
%%% Serializing
%%%
@InProceedings{Ernst92c,
author = "Michael D. Ernst",
title = "Serializing parallel programs (abstract)",
OMITeditor = "Charles E. Leiserson",
booktitle = "Proceedings of the 1992 MIT Student Workshop on VLSI and
Parallel Systems",
pages = "13-1 to 13-2",
year = 1992,
month = Jul # "~21,",
category = "Concurrency",
abstract =
"Programmers would like to be able to write a single program for both
parallel and serial computers. Historically, the focus has been on
parallelizing serial code. In this paper, we argue that the
reverse---serializing parallel code---is both more natural and more
efficient. We introduce and evaluate three methods for serializing
parallel code---unrolling, loop common expression elimination, and finite
differencing---and compare them to parallelization. All three methods are
based on a form of common subexpression elimination across loop boundaries.",
supersededby = "Ernst92e",
nonPAG = 1,
}
@MastersThesis{Ernst92e,
author = "Michael D. Ernst",
title = "Serializing parallel programs by removing redundant
computation",
school = MITEECS,
year = 1992,
address = MITaddr,
month = sep,
supersededby = "Ernst94:Serialize:LCSTR",
abstract =
"Programs often exhibit more parallelism than is actually available in the
target architecture. This thesis introduces and evaluates three
methods---{\em loop unrolling}, {\em loop common expression elimination},
and {\em loop differencing}---for automatically transforming a parallel
algorithm into a partially serial one that takes advantage of only the
parallelism available at run time. The resulting program performs less
computation to produce its results; the running time is not just improved
via second-order effects such as improving use of the memory hierarchy or
reducing overhead (these optimizations can further improve performance,
however). The asymptotic complexity is not usually reduced, but the
constant factors can be lowered significantly, often by a factor of 4 or
more. The basis for these methods is the detection of {\em loop common
expressions}, or common subexpressions in different iterations of a
parallel loop. The loop differencing method also permits computation of
just the change in an expression from iteration to iteration.
\par
We define the class of {\em generalized stencil computations}, in which
loop common expressions can be easily found; each result combines $w$
operands, so a naive implementation requires $w$ operand evaluations and
$w-1$ combining operations per result. Unrolling and application of our
common subexpression elimination algorithm can reduce its cost to less
than 2 operand evaluations and 3 combining operations per result. Loop
common expression elimination decreases these costs to 1 and $\log w$,
respectively; when combined with unrolling they drop to 1
operand evaluation and 4 combining operations per result. Loop
differencing reduces the per-result costs to 2 operand evaluations and 2
combining operations. We discuss the tradeoffs among these techniques and
when each should be applied.
\par
We can achieve such speedups because, while the maximally parallel
implementation of an algorithm achieves the greatest speedup on a parallel
machine with sufficiently many processors, it may be inefficient when run
on a machine with too few processors. Serial implementations run faster on
single-processor computers but often contain dependences which prevent
parallelization. Our methods combine the efficiency of good serial
algorithms with the ease of writing, reading, debugging, and detecting
parallelism in high-level programs.
\par
Our three methods are primarily applicable to MIMD and SIMD implementations
of data-parallel languages when the data set size is larger than the number
of processors (including uniprocessor implementations), but they can also
improve the performance of parallel programs without serializing them. The
methods may be applied as an optimization of a parallelizing compiler after
a serial program's parallelism has been exposed, and they are also
applicable to some serial programs.",
category = "Concurrency",
supersededby = "Ernst94:Serialize:LCSTR",
nonPAG = 1,
}
@Manual{Ernst92d,
title = "{EDB} Manual: An {Emacs} Database",
author = "Michael D. Ernst",
year = 1992,
month = Aug,
note = "For EDB 1.02",
omitfromcv = 1,
supersededby = "Ernst93a",
nonPAG = 1,
}
%%%
%%% Intellectual property
%%%
@Unpublished{Ernst92g,
author = "Michael D. Ernst",
title = "Partial List of Software Patents",
note = "Annotated on-line bibliography",
year = 1992,
month = Apr,
annote = "Available via anonymous ftp from
mintaka.csail.mit.edu:/mitlpf/ai/patent-list.",
omitfromcv = 1,
nonPAG = 1,
}
@Unpublished{Ernst92h,
author = "Michael D. Ernst",
title = "Intellectual property in computing bibliography",
note = "Annotated on-line bibliography",
year = 1992,
month = Apr,
annote = "Available via anonymous ftp from
mintaka.csail.mit.edu:/mitlpf/ai/index.",
omitfromcv = 1,
nonPAG = 1,
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1993
%%%
@Unpublished{ErnstY93,
author = "Michael D. Ernst and Gideon Yuval",
title = "A {Heraclitean} {CD-ROM} installer",
year = 1993,
month = Oct # "~27,",
note = "Microsoft confidential report",
supersededby = "ErnstY94",
omitfromcv = 1,
abstract =
"With most encryption schemes, the same decryption key is always used to
convert a particular codetext into plaintext. If a decryption key which
has been revealed to multiple parties is compromised, it is impossible to
determine with whom responsibility for the breach lies. RSA or elliptic
curve encryption can be used as the basis of a scheme which permits
multiple distinct decryption keys to each decrypt a two-part codetext.
Each decryption key encodes (in a public way) information about the party
to whom it was issued. Since decryption keys can be traced, their holders
have an incentive to keep them secret. We do not address the issue of
tracking decrypted information back to the decryptor; the plaintext is
identical for each recipient. Wide distribution of commercial software on
CD-ROM and pay-per-view video are among the applications of this scheme.",
nonPAG = 1,
}
%%%
%%% Konane
%%%
@InProceedings{Ernst93b,
author = "Michael D. Ernst and Elwyn Berlekamp",
title = "Playing {Konane} mathematically",
booktitle = "Articles in Tribute to Martin Gardner",
year = 1993,
editor = "Scott Kim",
pages = "6--15",
month = Jan # "~16,",
organization = "Atlanta International Museum of Art and Design",
abstract =
"This paper presents a combinatorial game-theoretic analysis of Konane, an
ancient Hawaiian stone-jumping game. The theory~\cite{BerlekampCG82} applies
particularly well to Konane because the first player unable to move loses,
and a game can often be divided into independent subgames whose outcomes
can be combined to determine the outcome of the entire game. Most modern
games, and most games that have achieved wide popularity, violate one of
these two basic assumptions and so resist combinatorial game-theoretic
analysis; notable exceptions are the endgames of Go, Domineering, and
Dots-and-Boxes. This paper first describes the game of Konane and the
ideas of combinatorial game theory, then gives values for a number of
interesting positions and shows how to determine when a game can be divided
into noninteracting subgames. The methods are most applicable to its
endgame.",
supersededby = "Ernst95:Konane",
nonPAG = 1,
}
%%%
%%% EDB
%%%
@Manual{Ernst93a,
title = "{EDB} Manual: An {Emacs} Database",
author = "Michael D. Ernst",
year = 1993,
month = Jun,
note = "For EDB 1.17",
omitfromcv = 1,
nonPAG = 1,
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1994
%%%
@InProceedings{WeiseCES94:POPL,
author = "Daniel Weise and Roger F. Crew and Michael D. Ernst and
Bjarne Steensgaard",
title = "Value dependence graphs: Representation without taxation",
crossref = "POPL94",
pages = "297--310",
abstract =
"The value dependence graph (VDG) is a sparse dataflow-like representation
that simplifies program analysis and transformation. It is a functional
representation that represents control flow as data flow and makes explicit
all machine quantities, such as stores and I/O channels. We are developing
a compiler that builds a VDG representing a program, analyzes and
transforms the VDG, then produces a control flow graph (CFG) [ASU86] from
the optimized VDG. This framework simplifies transformations and improves
upon several published results. For example, it enables more powerful code
motion than [CLZ86, FOW87], eliminates as many redundancies as [AWZ88,
RWZ88] (except for redundant loops), and provides important information to
the code scheduler [BR91]. We exhibit a fast, one-pass method for
elimination of partial redundancies that never performs redundant code
motion [KRS92, DS93] and is simpler than the classical [MR79, Dha91] or SSA
[RWZ88] methods. These results accrue from eliminating the CFG from the
analysis/transformation phases and using demand dependences in preference
to control dependences.",
basefilename = "vdg-popl94",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/vdg-popl94.pdf PDF",
NOTsupersededby = "WeiseCES94:TR",
category = "Static analysis",
csetags = "mernst,mernst-Static-analysis,plse",
summary =
"This paper describes the value dependence graph (VDG), a sparse,
functional, dataflow-like program representation based on demand
dependences. It also presents some of the analyses and transformations
that the VDG simplifies.",
nonPAG = 1,
}
@TechReport{WeiseCES94:TR,
author = "Daniel Weise and Roger F. Crew and Michael D. Ernst and
Bjarne Steensgaard",
title = "Value dependence graphs: Representation without taxation",
institution = "Microsoft Research",
year = 1994,
month = Apr # "~13,",
number = "MSR-TR-94-03",
address = "Redmond, WA",
basefilename = "",
supersededby = "WeiseCES94:POPL",
nonPAG = 1,
}
@TechReport{ErnstY94,
author = "Michael D. Ernst and Gideon Yuval",
title = "Heraclitean encryption",
institution = "Microsoft Research",
year = 1994,
number = "MSR-TR-94-13",
address = "Redmond, WA",
month = Mar # "~3,",
abstract =
"Most encryption schemes always use the same decryption key to convert a
particular codetext into plaintext. If a decryption key that has been
revealed to multiple parties is compromised, it is impossible to determine
who is responsible for the breach. Heraclitean encryption, which uses
public-key encryption (for instance, RSA or elliptic curve) as its
cryptographic basis, permits the encryptor to create as many independent
decryption keys as desired. Each decryption key can publicly encode
information about the party to whom it was issued, so that given a key,
anyone can determine its owner. Since decryption keys can be traced, their
holders have an incentive to keep them secret.
\par
We discuss applications of Heraclitean encryption, provide an example
implementation, discuss weaknesses in that implementation, and explore some
practicalities of using the scheme.
\par
We do not address the issue of tracking decrypted information back to the
decryptor; the plaintext is identical for each recipient. Heraclitean
encryption is applicable to any broadcast medium that can carry proprietary
information---for instance, pay-per-view video and wide distribution of
commercial software or databases via CD-ROM or bulletin boards.",
basefilename = "heraclitean-tr9413",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/heraclitean-tr9413.pdf PDF",
category = "Theory",
csetags = "mernst,mernst-Theory,plse",
summary =
"Heraclitean encryption permits an encryptor to create many independent
decryption keys for converting a particular codetext into plaintext.
This permits tracing of decryption keys and, in the event of a
compromise, determination of which decryptor leaked his or her key.",
nonPAG = 1,
}
@TechReport{Ernst94:SlicingTR9414,
author = "Michael D. Ernst",
title = "Practical fine-grained static slicing of optimized code",
institution = "Microsoft Research",
year = 1994,
number = "MSR-TR-94-14",
address = "Redmond, WA",
month = Jul # "~26,",
abstract =
"Program slicing is a technique for visualizing dependences and
restricting attention to just the components of a program relevant to
evaluation of certain expressions. Backward slicing reveals which
other parts of the program the expressions' meaning depends on, while
forward slicing determines which parts of the program depend on their
meaning. Slicing helps programmers understand program structure, which
aids program understanding, maintenance, testing, and debugging;
slicing can also assist parallelization, integration and comparison of
program versions, and other tasks.
\par
This paper improves previous techniques for static slicing. Our
algorithm is expression-oriented rather than based on statements and
variables, resulting in smaller slices. A user can slice on any value
computed by the program --- including ones that are not, or cannot be,
assigned to variables. The slicer accounts for function calls,
pointers, and aggregate structures. It takes advantage of compiler
analyses and transformations, resulting in more precise slices, and
bypasses syntactic constraints by directly constructing executable
slices. These techniques are implemented in a slicer for the C
programming language that accepts input via mouse clicks; operates on
the value dependence graph, a dataflow-like program representation that
is especially well-suited to slicing; and displays closure slices by
highlighting portions of the program in the programmer's editor.",
basefilename = "slicing-tr9414",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/slicing-tr9414.pdf PDF",
downloads =
"https://homes.cs.washington.edu/~mernst/pubs/slicing-9705-slides.pdf slides (PDF);
https://homes.cs.washington.edu/~mernst/pubs/slicing-9705-slides.ppt slides (PowerPoint)",
category = "Static analysis",
csetags = "mernst,mernst-Static-analysis,plse",
subcategory = "Slicing",
summary =
"Slicing helps visualize dependences and restrict attention relevant
program components. This paper describes techniques, and an
implementation, for slicing on arbitrary program values, omitting
irrelevant parts of statements, and exploiting optimizations.",
nonPAG = 1,
}
% Identical to Ernst94:Serialize:LCSTR
@TechReport{Ernst94:Serialize:MSRTR,
author = "Michael D. Ernst",
title = "Serializing parallel programs by removing redundant
computation",
institution = "Microsoft Research",
year = 1994,
number = "MSR-TR-94-15",
address = "Redmond, WA",
month = Aug # "~21,",
OPTnote = "Revision of Master's thesis",
supersededby = "Ernst94:Serialize:LCSTR A concurrently published technical report",
category = "Concurrency",
nonPAG = 1,
}
% Identical to Ernst94:Serialize:MSRTR.
@TechReport{Ernst94:Serialize:LCSTR,
author = "Michael D. Ernst",
title = "Serializing parallel programs by removing redundant
computation",
institution = "MIT Laboratory for Computer Science",
year = 1994,
number = "MIT/LCS/TR-638",
address = "Cambridge, MA",
month = Aug # "~21,",
OPTnote = "Revision of Master's thesis; also published as
Microsoft Research technical report MSR-TR-94-15",
abstract =
"Programs often exhibit more parallelism than is actually available in
the target architecture. This thesis introduces and evaluates three
methods --- {\em loop unrolling}, {\em loop common expression
elimination}, and {\em loop differencing} --- for automatically
transforming a parallel algorithm into a less parallel one that takes
advantage of only the parallelism available at run time. The resulting
program performs less computation to produce its results; the running
time is not just improved via second-order effects such as improving
use of the memory hierarchy or reducing overhead (such optimizations
can further improve performance). The asymptotic complexity is not
usually reduced, but the constant factors can be lowered significantly,
often by a factor of 4 or more. The basis for these methods is the
detection of loop common expressions, or common subexpressions in
different iterations of a parallel loop. The loop differencing method
also permits computation of just the change in an expression from
iteration to iteration.
\par
We define the class of {\em generalized stencil computations}, in which loop
common expressions can be easily found; each result combines w operands,
so a naive implementation requires w operand evaluations and w-1
combining operations per result. Unrolling and application of the
two-phase common subexpression elimination algorithm, which we introduce
and which significantly outperforms other common subexpression elimination
algorithms, can reduce its cost to less than 2 operand evaluations and 3
combining operations per result. Loop common expression elimination
decreases these costs to 1 and log w, respectively; when combined with
unrolling they drop to 1 operand evaluation and 4 combining operations per
result. Loop differencing reduces the per-result costs to 2 operand
evaluations and 2 combining operations. We discuss the tradeoffs among
these techniques and when each should be applied.
\par
We can achieve such speedups because, while the maximally parallel
implementation of an algorithm achieves the greatest speedup on a parallel
machine with sufficiently many processors, it may be inefficient when run
on a machine with too few processors. Serial implementations, on the other
hand, run faster on single-processor computers but often contain
dependences which prevent parallelization. Our methods combine the
efficiency of good serial algorithms with the ease of writing, reading,
debugging, and detecting parallelism in high-level programs.
\par
Our three methods are primarily applicable to MIMD and SIMD implementations
of data-parallel languages when the data set size is larger than the number
of processors (including uniprocessor implementations), but they can also
improve the performance of parallel programs without serializing them. The
methods may be applied as an optimization of a parallelizing compiler after
a serial program's parallelism has been exposed, and they are also
applicable to some purely serial programs which manipulate arrays or other
structured data.
\par
The techniques have been implemented, and preliminary timing results are
reported. Real-world computations are used as examples throughout, and an
appendix lists more potential applications.",
basefilename = "serialize-tr638",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/serialize-tr638.pdf PDF",
category = "Concurrency",
csetags = "mernst,mernst-Static-analysis,plse",
summary =
"This paper introduces and evaluates methods for automatically
transforming a parallel algorithm into a less parallel one that takes
advantage of only the parallelism available at run time, thus
performing less computation to produce the same results.",
nonPAG = 1,
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1995
%%%
@TechReport{Ernst95:Slicing_pointers_procedures,
author = "Michael D. Ernst",
title = "Slicing pointers and procedures (abstract)",
institution = "Microsoft Research",
year = 1995,
number = "MSR-TR-95-23",
address = "Redmond, WA",
month = jan # "~13,",
abstract =
"Program slicing restricts attention to the components of a program relevant
to evaluation of one expression, the slicing criterion. Our slicer,
which explicitly represents the store as an aggregate value, is the first
to support arbitrary pointer manipulations and aggregate values, and is
faster than more limited techniques. We also improve the asymptotic
complexity of slicing in the presence of procedure calls, and of a
preprocessing step for computing dependences of procedure returns on
formals. Additionally, our interprocedural slices can be smaller than
those produced by other techniques. We implement these techniques in the
first slicer for an entire practical programming language (ANSI C, except
{\tt longjmp}).",
basefilename = "slicing-tr9523",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/slicing-tr9523.pdf PDF",
downloads =
"https://homes.cs.washington.edu/~mernst/pubs/slicing-9705-slides.pdf slides (PDF);
https://homes.cs.washington.edu/~mernst/pubs/slicing-9705-slides.ppt slides (PowerPoint)",
category = "Static analysis",
csetags = "mernst,mernst-Static-analysis,plse",
subcategory = "Slicing",
summary =
"This paper describes how to efficiently extend program slicing to
arbitrary pointer manipulations, aggregate values, and procedure calls.
The implementation is the first for an entire practical programming
language.",
nonPAG = 1,
}
@Proceedings{IR95:proc,
title = "IR '95: Intermediate Representations Workshop Proceedings",
year = 1995,
editor = "Michael D. Ernst",
address = "San Francisco, CA",
month = Jan # "~22,",
note = "{\em ACM SIGPLAN Notices} 30(3), March 1995",
abstract =
"An intermediate representation is the basis of any tool for manipulating
computer programs. A good representation permits powerful operations to be
performed more simply, and may enable operations that a weaker
representation cannot support. This workshop will examine current trends
and research in the design and use of intermediate representations. The
workshop will include a mix of presentation and discussion periods to
facilitate interaction.",
basefilename = "ir95-proceedings",
downloads = "https://homes.cs.washington.edu/~mernst/meetings/ir95/ workshop website;
https://dl.acm.org/citation.cfm?id=202530 ACM proceedings",
category = "Programming language design",
csetags = "mernst,mernst-Programming-language-design,plse",
summary =
"This workshop examined current trends and research in the design and
use of intermediate representations for manipulating computer programs.",
nonPAG = 1,
}
@TechReport{IR95:tr,
key = "Ernst",
editor = "Michael D. Ernst",
title = "IR '95: Intermediate Representations Workshop
Proceedings",
institution = "Microsoft Research",
year = 1995,
number = "MSR-TR-95-01",
address = "Redmond, WA",
month = Jan # "~22,",
supersededby = "IR95:proc",
nonPAG = 1,
}
@Article{Ernst95:Konane,
author = "Michael D. Ernst",
title = "Playing {Konane} mathematically:
A combinatorial game-theoretic analysis",
journal = "UMAP Journal",
year = 1995,
volume = 16,
month = "Spring",
number = 2,
pages = "95--121",
abstract =
"This article presents a combinatorial game-theoretic analysis of
Konane, an ancient Hawaiian stone-jumping game. Combinatorial game
theory [Berlekamp et al.\ 1982] applies particularly well to Konane
because the first player unable to move loses and because a game often
can be divided into independent subgames whose outcomes can be combined
to determine the outcome of the entire game. By contrast, most popular
modern games violate the assumptions of combinatorial game-theoretic
analysis. This article describes the game of Konane and the ideas of
combinatorial game theory, derives values for a number of interesting
positions, shows how to determine when a game can be divided into
noninteracting subgames, and provides anthropological details about
Konane.",
basefilename = "konane-tr9524",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/konane-tr9524.pdf PDF",
downloads = "https://homes.cs.washington.edu/~mernst/pubs/konane-talk.ppt talk slides (PowerPoint, 1/17/2001);
https://homes.cs.washington.edu/~mernst/software/games.tar.gz implementation",
category = "Theory",
csetags = "mernst,mernst-Theory,plse",
summary =
"This paper presents a combinatorial game-theoretic analysis of
Konane, an ancient Hawaiian stone-jumping game. Combinatorial game
theory indicates, for a given board position, which player wins, and
how great that player's advantage is.",
nonPAG = 1,
}
@TechReport{Ernst95:Konane:TR,
author = "Michael D. Ernst",
title = "Playing {Konane} mathematically:
A combinatorial game-theoretic analysis",
institution = "Microsoft Research",
year = 1995,
month = aug # "~7,",
number = "MSR-TR-95-24",
address = "Redmond, WA",
basefilename = "konane-tr9524",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/konane-tr9524.pdf PDF",
supersededby = "Ernst95:Konane",
nonPAG = 1,
}
@InCollection{Boolos95,
author = "George Boolos",
title = "Quotational Ambiguity",
booktitle = "On Quine: New Essays",
year = 1995,
editor = "Paulo Leonardi and Marco Santambrogio",
address = "San Marino",
month = may,
pages = "283--296",
publisher = "Cambridge University Press",
note = "Draws heavily on~\cite{Ernst89c}.",
omitfromcv = 1,
nonPAG = 1,
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1996
%%%
@Misc{YuvalE1997,
author = "Gideon A. Yuval and Michael D. Ernst",
title = "Method and system for controlling unauthorized access to
information distributed to users",
howpublished = "U.S. Patent 5,586,186",
month = dec # "~17,",
year = 1996,
note = "Assigned to Microsoft Corporation",
abstract =
"A system for controlling unauthorized access to information distributed to
users and, more particularly, for controlling unauthorized access to
software distributed to users is provided. One method utilizing the system
of the present invention enables the software to be encrypted using a
single encryption key and to be decrypted using a multiplicity of
``decryption'' keys, each of which is unique to a particular user. The
``decryption'' keys are the products of numeric representations of
identifying information relating to users and unique user keys generated
using the numeric representations and a ``true'' decryption key. Since each
user receives a unique user key and both the numeric representation and the
user key are generated using the identifying information, if the user
reveals the numeric representation and the user key (or the product of the
numeric representation and the user key), the numeric representation and
the user key can be traced to the user who revealed them. Another method
utilizing the system of the present invention introduces randomness or
pseudo-randomness into the decryption scheme to provide an additional level
of security to the scheme.",
basefilename = "access-patent-5586186",
downloads =
"https://patents.google.com/patent/US5586186A/en Google Patents;
https://patentimages.storage.googleapis.com/d5/7a/e9/7233c72863437c/US5586186.pdf PDF",
category = "Theory",
csetags = "mernst,mernst-Theory,plse",
summary =
"This patent describes a system with unique decryption keys for each
purchaser of an encrypted product, so as to determine who revealed a
decryption key if one is made public.",
nonPAG = 1,
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 1997
%%%
@InProceedings{ernst-ijcai97,
author= "Michael D. Ernst and Todd D. Millstein and Daniel S. Weld",
title= "Automatic {SAT}-compilation of planning problems",
crossref = "IJCAI97",
pages= "1169--1176",
abstract =
"Recent work by Kautz {\em et al.}\ provides tantalizing evidence that
large, classical planning problems may be efficiently solved by
translating them into propositional satisfiability problems, using
stochastic search techniques, and translating the resulting truth
assignments back into plans for the original problems. We explore the
space of such transformations, providing a simple framework that
generates eight major encodings (generated by selecting one of four
action representations and one of two frame axioms) and a number of
subsidiary ones. We describe a fully-implemented compiler that can
generate each of these encodings, and we test the compiler on a suite
of STRIPS planning problems in order to determine which encodings have
the best properties.",
basefilename = "satcompile-ijcai97",
downloadsnonlocal =
"https://homes.cs.washington.edu/~mernst/pubs/satcompile-ijcai97.pdf PDF",
downloads = "ftp://ftp.cs.washington.edu/pub/ai/medic.tar.gz Medic implementation",
category = "Miscellaneous",
csetags = "mernst,mernst-Artificial-intelligence,plse",
summary =