+ All Categories
Home > Documents > Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ...

Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ...

Date post: 13-Sep-2020
Category:
Upload: others
View: 0 times
Download: 0 times
Share this document with a friend
29
Transcript
Page 1: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

����������� ��� ������������������������ ����������� � �!�"�$#%��& ')(���*�&+�$,

-/.103254�687:9<;>=@?BA-/./032DC�6FEG;�HBHB.

IKJ!LM?!6�.>9�N$./OPL3Q3?BJ�HSRUTWVXJ�2FTWJYZ23VX[�J!H]\^V@?^_�.�9�`aVXHBb1VX23Vc;N$0F;�HB=@./?B?dJ�\^[UVX=@=XJ�e�`$fhg/g/i1j/k

-/Q3=X_�g/klenm�i/i1o

prqtsvu�w/x@szyW{}|�qz~l���v��p$|����!�v�W����F�v�B�z�1���

���!�W�v�������!�z�����W�Z���U�� ��$��¡<�������@�W¡�¢S�z���£�W���F�z�U�W�d¤¥���t¡}��¦1�t¤§�v�d¨>©n ��t���¢K�t���ª��«�����¡<�t¤§�8�@�t¡�¢�¬�­®�B¯���£�t���3�z¡��ª¤v��­£­��B°Z±�²B³�´<µ�¶@·B¸v¨B�£�U«1�����®¤F�£�$¢S�z�� ��v¢a�����®¤¥�B¹v«�¬��3��¡<�z�>���@�W¡�¢a�����£�t�>���z�U°!�£�<¤¥¡��v���n��¦1�t¤¥�^� 1�B�t�n¡��d¤¥�v�£�t�B°�¡��^­º�����£�t�^­�»¼­£�£����­£�n�z�����v�!���£�W�U½U¾n >���8¦1��¦1�v¡8°!�v�t�^­��W¦��8�� ���¤¥�t�1¤§�v¦��8�z�U��¡¥�z���¿�@�t¡�¢a�]¯���£�t���3���À°!�£�¥¤¥¡��v���}��¦1�t¤¥�^�Á�£�$�� ��}¤¥�t�!���¥Â��Á���òzÄ!³�¶®±�²B³�´<µ�¶@·$Å^Æ�µB¸vÇ!´<Èɸ�Ê�²tťȥ¸v½l¾n ��n�1����¬�¡��n�z���� ��v�����¡<�������X�t¡�¢S�z�����W���M��¡��}ËW¬��£���}°Ì�ÎÍ��v¡��v�!�3�@¡��W¢��� ��t���}�v�1¤§�t¬��!���^¡��d°K�£��­£�£���d��¡F�z­£�t�v«>¡<�:«1�B¤v�z¬������� ��¬��1°!�v¡�­£»��£���S��¦1�t¤¥�^�Ï��¡��Z����¡���Ð!�£���W­�»G°!�ÑÍ��v¡��^���B½S¾n �����¡¥�z���¿�@�t¡�¢a�����£�t�G¦>¡��t¦/�v¡����£�v�¼�z�ZÒ<¤§­��W���d°ÌÓ1¨Ò<¤¥�W�����£��¬>�t¬���ÓÔ���1°ÕÒ��W¡<°!�^¡F¦�¡��^���v¡����£���WÓÏ��¡��}°!�§Ö1���d°K�z�1°¼�¥Â�¦�­£�W¡��d°�½3¾n >�}¤¥­®�z�����®¤8�t¡<��¦� ���¡¥�z���¿¯�@�t¡�¢a�z���£�t���B¨t ��W¢Z�W¢Z�t¡�¦� ��£��¢����1°K���t¦/�t­£�W�t�®¤v�z­����t¡��d¨U��¡��$�¥Â1��¢Z�£���d°K�£�S�� ���¤¥�t�!���¥Â�����F�� ��v���¦�¡��W¦1�v¡����£�v�B½¾n >�v� ©8�Z°!�¥Ö1�>�×��·tÈ^Æ�ȧ³c¶@µ�ÄS©n ��®¤� �©Á�K«1�v­£�£�v�W��¦�­®�B»��¼�G¤¥�v�!��¡¥�z­n¡��t­£���£� °!�£�<¤¥¡��v���S��¡¥�z���¿¯

�@�t¡�¢a�z���£�t���B½FØ}�!����¢S�z��¡��t�®°K¤¥­£�t��¬>¡��$��¦1�t¤¥�^�d¨l©n ��v�G¦1��¡����º��­£­�»K�t¡¥°!�v¡��B°�¨U¤v���G«1�¼�£�!���v¡�¦�¡��v���d°Õ�z�­º�������º¤§�v�d½8Ù��$�� ��z©5�� 1�z��°!�v­£�v�����W���}�£�1°Ì¬1¤¥�$­£�z©8�v¡}���v¢Z�£ ��W¢Z�t¢¼�t¡�¦� ��£��¢��r«1�v��©8�v�v�Õ�� >��¤¥�t¡�¡��¥¯��¦/�t�1°!�£���¼­®�z�����®¤¥�v�B½

Ú¥Û3Ü¥Ý�ܧÞ^ß�à�á�Ý�âWãtã!äBß�å�Ü<æ�çÎè�ã!Þvß�å8ézê�ë8ìníGîBß�Þ^èzåªë8í/ïcð/ñnòBó¥ïcôBóBíUÛFõBódõBó^öt÷

Page 2: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

� ������������ ��������

���Py��>x��vsB�vqz�vq��§~Uy�sBq��q��Gqty!w"y��¥qz���! }qB{ºq"� qzw1���$#F~U�Ìxºw/���"#3�>�����^u�qz��~�u�qzw��%� qzwUy��$u/x@svu&��q'��x£{�{( qzw�qz�¥x@szyW{£{)� szyW{£{3�%*��,+.-0/�1325476823#%�/qzw����vq5��9:�<;>=�?�w@�>x)A�x��:*UyW{8~U�!x®w/���n�B �;C��x£{�{�9lq��/qzw����vq5��9:��{®�B��qz�szy%�¥q×{ºqz�^�vqz���"DE0F�GBF3H)H)HIFKJLFNM.F"HIH)H0OP;>=<���&Q%R<#L�q��GqtyÌw)�vu�qS~U�B��qz���¥qz����wS;>#F���ZsB�!{£{®qtsB�¥x®��w%�B $yW{£{�T*U9@�¥qz�V���B W;>=WX8{®q"�Gqzw/�����B YQ R �qZ�Ôx�{£{W�/qzw����vq'9.��*�~�~Uqz��szy%�¥q¼{®qz�v�vqz�V�"D\[]F7^�FN_>FN`\FVaZ=pÔu��v�%* ( u��%*��8�vu/x��n~UyÌ~Uqz����q\��x£{�{b9Uq�sB�>wUsBqz�vw�q5����x®�vu' c*�wUsB�¥x®��w@�"#��>�n��~Uqz�dyÌ�v�����"#B�/qVdUw�q5� ��w<Q R #

x®w sB��w/�v�dy%�¥�:�v�' e*�wUsB�§xº�>w@�,�/qVdUw�q5����w�;>=�f)q�szyW{£{Á�vu�q"�hg5i3jbk�l"mKnbipoqjUg5rsn�k�l%#�y!w@����qt��x£{�{��/qzw����vq�vu�q"�u*@��x®w ( y�~U�:�¥�TdUv5w����By!�¥x®��w"x®ww�$u/x@s^u%�vu�q���~Uqz�By!�v���"xW�v�dy!w@�y ����N�Õy!�¥x®��wq�z�.��9U�Ì{x����¥qz~Uy!�By!�vq5� ��v�%� x®����~��vqtsBq5�>x®w ( ��~lqz�dy!w@�0x�yÌ� ( *U�Gqzw/�,9:� y�{U254V/�|3}%=\f)qZw��>�dy!�¥x®��wUyW{£{)�PsB�>w: c���7� �v�G�vuUyÌ�, ��%*�w@�x®w�~Î�3��x®ww�$u/x@s^uP9/x®wUy!�N�%�>~Uqz�dy!�§xº�>w@�Gy!�vq��/qzw����^q5�S9.� x®w:dUv�qVv ~��vq5�7��x®��w@� yÌw@�S*�wUy!�N� ��~Uqz�dyÌ�¥x®��w@�y!�vq�/qzw��>�vq5��9.���z*:�<v+qVv�~��vq5�N�<xº�>w@�"=W���>�$qVvÀy!�G~/{®q%#/xI �Q R ��b� Q R x���y×�v�dy!w@�y ����N�Õy!�¥x®��w<� yÌ~�~/xºw (�T*U9@�¥qz�V�S�B ; xºw/�v�)�>�vu�qz�<�T*U9@�¥qz���S�! �;>#:�vu�qzwS ����<_>FN`���;>#W��q����%*/{��w*@�¥q��vu�q�qVv�~��vq5�N�<xº�>w� _��<`��VH����v���/qzw����vqZ�^u�q¼x��Õy ( q��B n�vu�qBx®�$x®w/�vqz���¥qtsB�§xº�>w�=

� w�q,�T*Us^uZ�^�dy!w@�y ����N� yÌ�¥x®��w�x��8yt*�w/xs�p*�qB{)� ( qzw�qz�dy!�vq5�'�%�sn�lB��i3�Z��~lqz�dy!�v�>�5#���#B9:��$u/x@s^u���q��Gqty!wy' c*�wUsB�¥x®��wqQpR ��b� Q%RC�vy!�¥x��y c�>xºw ( �vu�qZs^{®�.�T*��^qay3v/x®�%���"D

_u�w_qH��_u�w` x�� ~/{�x®q5�t_>H��S�w`\H��_>H��WH��&��_qH����t�P_>H��_>H�� �P`�H��"x)�G~/{£x®q5� � _��<`<��H��&��_qH�� �P`\H��

p�u�q�{@y%�¥�$y3v/xº�p� x��}w��>w��K�¥�dy!w@��y!�V�b=�?��:x���w����:uUy!���Õ�v���¥u��B� �^uUy!�s^{®�.�T*��^q���~Uqz�dyÌ�v�����¡�$u/x@svu��vyÌ�¥x��y e��vu/x��$y%�U�>x®�¥x®��wUy�{ªy3v/xº�p� y!�vqt*�w/x��%*�qB{)� ( qzw�qz�dy!�vq5� x®w �^u�q¢�¥qzw@�§qZ�vuUy!�� ����$y!w:���¥qz�,`�#1�^u�qz�vq�qVv1x��¥�V�$y*�w/x��%*�q��Sx®w/x)� yW{��¥qz�,_u�w`£�T*Usvu��^uUy!�,_>H�� �P`�H��W= � w�qSszy!w yW{��¥���§u����C~®�5¤3�F�vuUy!�¥�¦ �:n�i3�@o¨§@©c§Pª�«3¬­|!68+:4T2<|V{®234T¯%°c|%4�/)6�+.-0/�±3+.23¬I²�³p25-@234T¯%°c2�}�/ ´�¯p-@}�|p-@¬I²</ ´µ/¶°�68¯p°c/)6¶·�2$6°¶¸.2�¯p-@°c/s¹2"ºB«"¸.¯p-.³%2»{�4T|V{U254V°c²

/ ´WJ�FVM<¼O�_>H��½°¶¸.23-�J�O � _�¾�¿�MpÀ%��H��½/¶Á»{�¬I/�2$6ÂM�¼O � _£¾�¿�J�À%��H��\Ã?�wPsB��w/�v�dyp�¥�5#Uy!w:���¥qz�¼�B nqB{ºq"� qzw1���Z;Ä��x®�vu)y!w �>~Uqz�dy!�^����ÅS�vy!�¥x��y c��x®w ( �vu�qZdU�V�¥���^u��vqzqas^{®�.�T*��^q

y3v/x®�%���"#��^� ( qz�vu�qz�\��x®�vu��vu�q�Æ��vqBx®w/x®�NÇz�KÈ"y�s"ÉFy!w�qSqVvUsvuUy!w ( qZy3v1x®�%�xI ]J�F�Mµ¼O�_qH�Å �^u�qzw�J�O � _�¾�¿�MpÀ%�VH�ÅÕx)�G~/{£x®q5�M'O � _�¾�¿�JbÀ%��H�Å

x�� szy�{�{®q5� y�Á�¯p°c4Ê|p/�}S~®�5Ë3�~®�!Ì8��~�Q3�K=�Í�μw:�P�¥qz��; yÌw@��s^{®�.�T*��vq���~Uqz�By!�v�����Ï�^y!�¥x��y c��x®w ( y!w y!w/�¥x®�qVvUsvuUy!w ( q y3v/xº�p��# � ;>F��¡��#lx��Zszy�{�{®q5� y!w&jbk@g5rÐo>jUg5i5nbr�ÑÒ~Î�!�,~Î�3�K#3����%�sn�l!��i3�wl5ÓLj@�B�w~®�5¤3�K= � � �vu�qz�sB�%�<� ��w"wUyB�Gq5�» ������^u/xs�KsB��wUsBqz~��ayÌ�vq�ª�ÔWÕ&³%4T2V2�}%|p/�}BÖ\6V¸.25¬¶¬I/�-:³×68°c4V+.«3°c+.4T2�~IÌ"�K#�¯%¬I/I³%-@Á�23-@°W~�¤B�K#l���«V|%-@132"º¢³p2�|pÁ�23°c4�²�~�Ø3�3~��v�BA>xs�/q5� ��w/{)� �^uUy!����w�qt e*��^�vu�qz�$�vq5�p*/x®�vq5���vu�q�q"�G~��T���§qz�5#0Ù�#/�v��9UqZs^{®�.�¥q5�b=ÚyÛ átÜnàyÜÎäBÝ�âtß�Ü}äBã!Ü¥ß�Þvå�äBßYÝ�äNÞMÞ�ß$Þ^å�ß�ävçÎæ¼çÎÝ8ètäBßcß$ÞTÜàÜÎê�àvÞzÜàÜÎÜ<æKå�átÜnÝ�ã!ÞvèWèzçÎètî¼äBã�Ü¥ß�Þ^å�ädߥ÷áNâ ÜÎädÝ�âWß�Ü�Ý�ã�Þ^à¥Ü<Ý$Þ^ß�Ü\Þ@Þvß\ß�äBß�Ü�ÞvéWâtèWæ�Þ^èzå$å�á�Þ^è äBètÜ»ß}çÎîBázå$ÜTãzã!Ü¥à<å¥÷GðWädß:ÜTãtÞNß�ã"ÜÎÜVäFå�áWÜ<ß�Ü�ÜÊãBçÎÝ�å¼Þvå¡ÜÎܧÞ^Ý�å$õdòBõæzçÎÝ�åXçÎèWà¥åÁàyÜÎäBÝ�âtß�Ü}Ý�ã!Þvà¥Ü¥Ý8à<äVß�ãtßXçÎÝ�Ü¥æ�ä7ÞÀó:ÜyÜÎÜTßÜ¥èzå�Ý¥÷�å¼äBß�ÜnîBÜ<èWÜ¥ß�ÞTÜàÜÎêVä�çÎårà§Þ^è¼é�ÜnÝ�áWäNæFè¼å�á�Þ^å3å�átÜ¥ß�ÜnÜTãBçÎÝ�å]ß�äBß�ÜÁå�á!Þvèç%è æzçÎÝ�åXçÎèWà<åTä/ètäBèzï®çÎÝ�äVß�ädß�ãWázçÎà$àyÜÎäBÝ�âtß�Ü�Ý�ã�Þ^à¥Ü¥ÝÁãWß�äNéBçÎætÜ¥æ ç�ê�ë òtì ë óTíX÷�îBç�ß:çàÜ�Þ^߶ÜÎêVä å�áWÜ¥ß�Ü}Þvß�Ü�ß$Þ^èzê�æ�çàïÌÜ¥ß�Ü¥èzå8àKÜÎäBÝ�âtß�ÜäBã�Ü¥ß�Þ^å�ädß�ÝTä.ðl÷

Q

Page 3: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

��� �^u�q��@�0k��Ui3jUg"n�iS�B �_ #/���»9Uy%��x������B �_w#®�/qzw��>�vq5��_qH��W#:�qZ� qty!w y��Sx®w/x)� yW{W�¥qz�,`h�T*Usvu��vuUy!�`\H�� �P_qH��W=���xs�¼y!w����^u�qz�,��qB{�{®�K�/qVdUw�q5���v�dyÌw@�y c�>�N� y!�¥x®��wÕ�B WQ R x®w/�v��Q R =pÔu�qÔs^{@y%�7��x@szyW{��$y3�Z�B ��>x��vsV*@�N��x®w ( �vu�q�~��v��~lqz�v�¥x®q5�:�B @ c*�wUsB�¥x®��w@�8x��ªxºw �vqz�N���8�B 3�vu�q��v��~l�!{®� ( x®q5�n�B

�vu�qBx®�Z�/�%� yWx®w@�¼y!w@��sB�®�/�p� yWx®w@�"=\f)qZ��x£{£{�*@�¥qas^{®�.�T*��^q��¥~Uy�sBq5�¼y%�N�§� s^x@y!�vq5� ��x®�vuPy×�>xs�^sB�vqz�vq��§~Uy�sBq%#;>#>x®w���*Us^uÕ�vu�q¢�^yB�Gq,�$y3�%#1y%�:�vu�qt*�w@�/qz�¥{)�>xºw ( �¥�v�N*UsB�N*��^q�9:�<�$u/x@s^u��v���>x��vsV*@�N�Ô�vu�q�~��^��~Uqz�v�§xºq5�:�B yS�v�By!w@�y ����N� y!�§xº�>w´"=

μw/�¥x)� y!�v�v�Ìxs�"s^{®�.�T*��^q��¥~Uy>sBq5��uUy3A�q�9Uqzqzww�¥�N*@�>x®q5��xºw½~®�5¤3�K#lx®wS�$u/x@svu �vu�q��T*U9@�¥qz�V�Z_>FN` �Ï;y!�vq�~UyÌ�v�¥x@yW{£{)�������/qz�vq5��9:� ��u��u�qz�vq%#

_ �� ` xI y!w@�Õ��w/{)�ÕxI `��<_>H��S�w_u�w`\H�� � �B�p�u/x���x��ay�~Uy!�^�¥x@yW{���V�/qz�Z��w½¯%¬¶¬3�vu�q��z*U9@�¥qz���K�B �;>#nw�����Ê*@�¥��x®���Ss^{º�:�¥q5�w�T*U9@�¥qz���$=�?��Kx��K~U�.�N�<x�9/{®q�v���¥u��B���^uUy!���^u/xs�¼~UyÌ�v�¥x@yW{n�����/qz�¥x®w ( �B �Q R xs�$#lxºw ¿y�sB�3#My×��qB{�{��§�v�N*UsB�N*��vq5�+{@y!�v�¥x@sBq%# �t#FszyW{£{®q5�"�vu�q�%�sn�l!��i3�q�sjUg"g5r¶�B�"�B ¡;>=��rx ( *��vqG� � y:�8x£{£{)*@�¥�v�dy!�^q5��yS�T�/~/x@szyW{ªs^{®�.�T*��vq�{@y!�v�¥x@sBq%=p�u�qG�^q ( */{@y!�¥x®�T� �B ,�¥�v�N*UsB�N*��^q��T* (%( q5�§�vq5� 9.���vu/x��td ( *��vq �vqtyW{£{)�PqVv/x��¥���"#�«�à ´$à ~®�5¤3�K=Sp�u�q sB�!{£{®qtsB�¥x®��w�B ,�%�)nbl"�Uѽ�T*U9@�¥qz���"#0 ����Z�$u/x@s^u&_ �Ï_qH���#0 ����N����y {®�B��qz��¥q"�Sx)�G�U�:*/{ yÌ���T*U9/{@y!�v�§x sBq ~IÙFNj����%ÑL�U�K#�/qzw����vq5� x®w��vu/x���d ( *��vqt9.��9U�Ì{s�/qz�Z�¥�v�§xºw ( �yÌw@��<�!x®w�q5� 9.���§�!{£xs�+{£xºw�q5���vuUy!�$y!�^q ( qzw�qz�ByW{£{��Õx®wUs^{£x®w�q5� ��v�%� �vu�q�{®�B��qz��{®qV c���v�G�vu�qZ*�~�~lqz���¥x ( u/�,�$u/x@s^uq�/qzw����^qasB�BA�qz�¥x®w ( �vqB{@y!�§xº�>w@�¥u/x®~@�"=��pÔu�q ( qzw�qz�dy!�^�����"#%GBF��BF��pFWG��BFWG��%F��Sy!w@�����%#/y!�vq$sB��w�w�qtsB�vq5� �v�K�vu�q�sB���v�^q5�¥~U��w@�>x®w ( s^{º�:�¥q5���§qz���

�vuUy!���vu�q"� ( qzw�qz�dy!�vq'9.����y%�¥u�q5�+{�x®w�q5� ( qzw�qz�ByW{£{�� x®wUs^{�x®w�q5� ��v�%� {º�B��qz�$�¥x ( u/�$�v� �vu�qZ*�~�~Uqz�¼{®qV ��5=W?��szy!w<9lq¢�§u�����wG�vuUy!�nqty�s^uÕ�B M�vu�q�{@y!�v�¥x@sBq�x®w/�vqz�NA!yW{��Z~à_>H���FN_>H��b��x��:yZ9U�/�!{®qty!w {@y!�v�¥x@sBq%=�?�w �vu�q¼szy%�¥q$�B �vu�qS���T*U9@�§qz����sB�p�G~��¥x���x®w ( ~àj����pÑ��bF����"�ÁyÌw@�&~àj����%Ñ\F��%�y#U��q�x®w@�>x@szy!�vqS�vu�qBx®�ZsB��w@�¥�¥x®�N*�qzw/�¼qB{ºq"� qzw1���y!w@��y<��yp�¥u�q5���%*��§{�x®w�q%=pÔu�q��/���v�vq5�a{�x®w�q5�t�/qzw����vq�y¢ cq"� �B F�vu�q¼sB��A>qz�¥x®w ( �^qB{ yÌ�¥x®��w@�¥u/x®~@�\9Uqz�T��qzqzwÕw���w���s^{®�.�¥q5� qB{ºq"� qzw1���

x®w&�>x��Fqz�vqzw/�Z9U�/�!{®qty!w�x®w1�^qz�NA�yW{��"=Kp�u�q5�¥qGsB�BA�qz�¥x®w ( �^qB{ yÌ�¥x®��w@�¥u/x®~@�"#���u/x s^u>��q��/qzw����vq�9:��_ � � aZ#�/�Kx®w@�/qzq5�Õqtsvu��S�vu��.�§q$�B F�vu�q�s^{º�:�¥q5���z*U9 ( �dy!~�u��T*U9/{@y!�v�¥x@sBq%=�?�wÕ~Uy!�v�¥x@sV*/{@y!�5#:��q$uUy3A�q¼�vu�q\ ��!{£{®���Ôxºw (�vq5�T*/{®���»�$u/x@s^uPszy!w�9lqZ ��%*�w@� x®w ~®�5¤3�K=¥�¦ �:n�i3�@o¨§@© �"!�#¡��k�ÑLjboq�0k@g"j@��$n&%b�Ui�rÐk'� ¥�¦ �.nbi3�@o)(+*)´WJ>¼O�_ °¶¸.23-

, ¯�- _ ��>_�¾�¿�J�À�/ ´�¯%-@}�|%-0¬­²×/ ´WJ>¼O�_>H��,�. -£_�¾�¿�JbÀ/�� _ / ´�¯%-@}�|%-0¬­²×/ ´WJ�O�_>H��

0 ¸.234Ê2 , ¯�-µ/s6¯�«V|%15234Z/ ´¯%-0}�|p-@¬I²</ ´ � _£¾�¿�J�À%��H�� �P_qH���¾ ¿�JbÀ�¯%-0},�. -</)6¯%¬ 0 ¯%²36¯�«�|p15254V/¶-.³�4T25¬I¯%°c/¶|%-U6V¸./ {�Ã

1q|p4Ê2V|%132547ÖW/ ´��Ò/s6+.-0/�±3+.23¬­²'³%25-0254T¯%°c2V}�°¶¸:25- , ¯2-�¯%-@} ,3. -�«"¸.¯p4ʯp«5°c254V/5482�¯%¬¶¬�«V|%15234�/¶-.³�4T25¬I¯%°c/¶|%-U6/¶-� Q R F+��S�"Ã

6 Û átÜ:å�Ü<ßcß87�é!ÞvÝXçÎÝ:9�á!ÞvÝnÝ�ä»ßÔÞ^èzê�à¥ädèWètäBå�ÞvåXçÎäBètÝTä�Ü¥Ý�ã!Ü¥à�ç�ÞzÜàÜÎê�æ3çÎå�áZß�Ü¥Ý�ã!Ü¥à¥ånå�ä,édÜ¥à¥å�äBßÁÝ�ã!Þvà¥Ü¥Ý}ÞvèWæZå�áWÜ�çÎßnà�á�Þ^ètîBÜä7ÞUé�Þ^ÝXçÎÝTä�å�á�Þ^å�æ3ÜÁãWß�ÜKޮܥßFå�áWÜWß�ädß�ÜnèWÜ¥âtå�ß�ÞzÜ;7¿îdÜ¥èWÜ<ß�Þ^å�äBß:9t÷

< Û átÜ0ÜÎäNæ3Ü¥ßUÝ�ÜTß:ç�ß�äzætâ"Ü�Þ^ßXçÎåXê$äNÞ�àyÜÎäBÝ�Ü<æ�Ý�âtétÝ�Ü¥å�Ýlã�Þ^ß�åXç�ÞTÜàÜÎê$äBß�ætÜ¥ß�Ü¥æ�ézê8çÎètàyÜÎâtÝXçÎäBè¼á�Þ^ÝUé!Ü¥Ü<è�ß�Ü¥ã!ÜvÞvå�Ü¥æ"ÜÎê�æ�çÎÝ�à<ä7édÜ¥ß�Ü¥æézê,ß$Þ^èzêÏÞ^âtå�áWädß�Ý¥÷�îzÜ¥ÜWå¼äBè>=�Þvß�æWÜ¥åWì ë�ë í%Þ®ädß8Þvè�çÎèzå�Ü¥ß�Ü<Ý�åXçÎèWî�Ý�â5ß\ß$Þvß�êB÷

Page 4: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

bcde

abcde

de

ad

d

bcd

abde acde

cde

acdabd

cdbd

abcd

bdeade

be

abc

bceabe

ab

bc

b

abce

ace

ceae

e

ac

c

ab

c

d

e

(a) (b)

Ø

a

�rx ( *��vqG�%D�Î��n{®�.�T*��^qÉFy!�v�¥x@sBq%# �

$nbi5nb���sj@i���§0©�����25°�` �� a�Ã, ¯�- *)´Za½�P`Ò¾�¿�JbÀpÖW°¶¸.25- . |%°¶¸�` ¯%-@}×a ¯%4T2�«5¬I|B6"2V}.Ã,�. - *)´Za½�P` � ¿�JbÀpÖW°¶¸.25- a /s6-@|%°�«5¬I|B6"2�}.Ã

���0oSoqjw§@© *)´�� /)6Z+.-0/�±3+.23¬I²³%23-@254T¯%°c2V}BÖW¯%-0}�/ ´Zaϼ� Ù£/)6«3¬I|B682V}BÖ, ¯�-,J�O>a,H��P/ ´�¯p-@}�|%-@¬I²</ ´Za � ¿�JbÀ�/s6«5¬I|B6"2V}BÖ/�- 0 ¸./¶«"¸�«V¯B6"2Za,H�� � ¿�J�À� � a � ¿�JbÀp��H����,�. -ZJ�F�M'O>a,H��P/¶Á»{�¬I/�2$6°¶¸.254T2�2"ºB/)6"°W«3¬­|!682V}<6"25°¶6\`� .F7`����½a

68+:«"¸�°¶¸.¯p°�J�O ` F�M'O�` � ¯%-0}�J>¼O�` � F�M�¼O ` �, «�-�/ ´ZÙ�H�� � ÙZÖW°¶¸.254T2�2"ºB/)6"°¶6WJ�O>aC68+:«"¸�°¶¸.¯%°�¿�JbÀ�/s6«5¬I|B6"2�}.Ã

Page 5: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

¥�¦ �:n�i3�@o¨§@©��"!�#¡��k�ÑLjboq�0k@g"j@���bg5i%���BgB��i3� ¥µ¦ �:n�i3�0o/( ��25°p_qH�� ��&`\H��&¯p-@}t¬­23°:_ O&~à_>H���FN_>H��b�ÊÃ��¸.234T2�2"ºB/)6"°¶6�¯w+.-0/�±3+.2�` Oh~à`�H���FN`\H��b�6"+:«"¸w°¶¸.¯%°,_ ��>`�Ö 0 ¸.234Ê2�` /s6�Á�/¶-@/¶Á�¯%¬ 0 4�°Kà ��, Á�¯!º�/¶Á�¯p¬ 0 4�°Kà � -pà 1q|%4T2V|%15234,` �Ò_ ¾�� 0 ¸.234Ê2��Ä��`\H�� � _>H��Ò¯%-@}×` ��`\H�� �� 0 ¸.234T2� �P_>H�� � _ Ã

�rx ( *��vqS� � y:�3x£{£{)*@�¥�v�dyÌ�vq5�:�vu/x��}�^u�qz���vq"��=�X�A>qz�N�Sx®w1�^qz�NA�yW{�~à_>H��WF7_qH��@�MszyÌw�9lq�~��v� <qtsB�^q5��V*�~:�ÔyÌ���U���U=���5p�u�qz���^q"� �p=�QU#8q"A�qz�N�5sB�BA�qz�§xºw ( �vqB{@y!�§xº�>w xs�'� yÌ�� �q5� 9.�)�^u�q��>x �Fqz�vqzwUsBq��B �T*@�¥�S��w�qÕqB{®q"�Gqzw1�9Uqz�T��qzqzwG�vu�q¼�T���¢�¥qz�V�"= �}��w@�¥q5�p*�qzw1�§{��%#>x®�$szy!w<9lq$x£{£{)*@�¥�v�dy!�§x�A>q��v��{@yB9UqB{ÁsB�BA�qz�¥x®w ( �^qB{ yÌ�¥x®��w@� � q5� ( q5�V���x®�vu��vu�qZsB���v�vq5�§~U��w@�>x®w ( qB{ºq"� qzw1�5=

?�w��%*����/q"A�qB{®��~U�Gqzw/� �B ��v�dyÌw@�y c�>�N� y!�¥x®��w@�'��q���x£{£{�y�{s�§�&*@�¥q �^u�q� c�!{£{®�B��x®w ( {®q"�<� y%�"#��$u/x@s^uuUy3A�qS�vu�q' cqzqB{£x®w ( y!w@���My3A����¼�B �vqB{@y!�§x�A>qG�v��~l�!{®� ( x®q5�"=�É3qz� � ;>F��¡�,9UqÕy!w.�"s^{®�.�T*��vq��§~Uy�sBqGy!w@� {ºqz�� �P;>=W���Õ�vu�q�i3�Ul"g5iBr��!g5r)nLk n0m��Sg"n�� #0�/qzw����vq5�������Z#U��qZ�Gqty!w

`�H������½�P`\H�� ���SF���`£���SHf)qZ��x£{£{}yW{��¥� szyW{£{n�vu/x��$y<i3�®�sjUg5r5%��&�%�sn�l!��i3�b=���0oSoqjw§@©��Ò����� /s6¯�«5¬I|B6"+.4T2'|V{®234ʯp°c|%4NÖ 0 ¸./¶«"¸�/s6+.-0/�±3+.23¬­²'³%25-0254T¯%°c2V}</ ´�� /s6$Ã

��� �!�#"�$%'&)(+* �d¤^�z¬�����,.-0/�¨1,2-3,54 6879/;:<,54 6>=@?$½%BAC(+D �v�>,2-FEG-�/�½H,54I6>= ? :0,54I6J79/K-FEL4 6�7M/N:<EO4I6>= ? ½%BPC(�% ,54I6>= ? ( 4 6L= ? : % ,54I6Q7M/ ( 4I6>= ?

: % ,54I6Q7M/ ( 4I6J79/-3,54 6L4I6J79/R4I6875/:,54I6875/S:<,54I6T=@?

¾n ����t�� >�v¡}¤¥�t�!�¥�z�£��¢Z�^���r�@�W­�­£�z©n�3�X¡��t¢ %U&)( ½%�VW(+D �v�>6Õ«1�:¬����®ËW¬��v­£»¼�t�v���^¡<�z���d°S�z�1°¼­£�v�L,54I6>=I?3:0EL4 6>=@?$½H,54I6�78/;:<EO4I6X78/ �£¢K¦�­£���^�Y,54I65:<EO4I6

% ���£�1¤§�Z,54I6�-[/ �z�1°8EO4I6�-[/ ( ½]\!�1¨^,54I6>=@?F:<,54 6879/;: % ,_7`E ( 4I6J7M/S: % ,a78E ( 4I6>=@?$½>b

$nbi5nb���sj@i���§0©�c ªZ-@² 68+ . 6"25°X� |T´q¯%-½¯%-0°c/�Á�¯%°c4T|%/¶}w«5¬I|B6"+:4Ê2 6y{®¯%«V2 ,ed F�� -q³p25-0254T¯%°c2"6�¯w«V|%4�4T2$¹6y{®|%-0}%/�-:³�6"+ . 6K{U¯%«V2 � � FV�f���t�8Ã

ÎZ�W�§u�����w�9lqB{®���'#1�^u�q$�vq5�¥�v�§x sB�§xº�>w �B FyZs^{®�.�¥q5���¥qz����x£{�{FyW{)�$y5�U��9lq�s^{®�.�¥q5�b=}pÔu�qÏyB9/x£{£x®�T�G�v�¼x®w: cqz��vuUy!�'_ x��Ss^{®�.�¥q5�S�$�^�5=��½�$u�qzw xº�V�Z�^q5�¥�v�¥x@sB�¥x®��w x��as^{®�.�§q5�&�$�^�5=������ x��K�B ,�G���vqSx®w/�vqz�vq5�¥�3= p�u�q ��!{£{º�B��x®w ( {®q"�<� y ( x)A�q5���T���µ�z*:�+s^x®qzw1��sB��w@�>x®�¥x®��w@�"=�g$qBx®�vu�qz��x���w�qtsBq5�N�vyÌ�N�%=���0oSoqjw§@©�h

, ¯�- _ «3¬­|!682V} 0 4V°KÃ,� /¶Á»{�¬I/�2$6�_��R� /)6Z«5¬I|B6"2�} 0 4V°KÃ\������Ã

Ø

Page 6: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

,�. - *)´ � /)6Z«5¬I|B6"2�} 0 4V°KÃ\� ¯%-0}_u��� Ö�°¶¸.23-_ «5¬I|B6"2�} 0 4�°KÃ\�����h/�Á»{�¬I/¶2"6,_ /s6«5¬I|B6"2�} 0 4V°KÃ,�\Ã

, «�- *)´,_ /s6Z«5¬I|B6"2�} 0 4�°KÃ\��� � ¯%-0} � _>H�� � _S��� � ; � � �W� ÙZÖW°¶¸.23-_ «5¬I|B6"2�} 0 4�°KÃ\�,Ã

��� �!�#"�$% � ( �X�Y, �£�ª¤¥­£�W���d°S©n¡��d½]6 �� ��v�9,54 69:0, �z�/°

% ,_79/ ( 4I6O= ? -�,54I6T= � 75/+4 6>= ? :<,54I6J79/ 79/S:3,_79/�½% « ( ,h¤¥­£�t���d°S©n¡��d½]6>= ? �£¢Z¦�­£�£�v�],54I6875/ :0,�½

* ¬��>,2-�/ ���1°9/ ¤¥­£�t���d°S�£¢Z¦�­£»�,54I6�-[/�¨!���`,54I6J79/S:3,54I6R:<,�½% ¤ ( �X�Y, �£�Á���W�}¤¥­£�t���d°S©n¡��B½]68¨��� >�v� % ,54I6 � , ( :��S½

D �v��� «/�n¤¥­£�t���B°$©n¡��d½]6>= ? �����[:3,54I6>= ? � , : % ,54I6>7�/ ( � , : % ,54I6 � , ( 7�/�½8�W�����BËt¬>�v�!��­£»�G-�� � /�¨����1° % ,54I6 � , ( 7 % � � / (� :��¼½>b

� �>���t�����3�������\�����Z���

���)y�g5i3jbk�l$mKnbi%o>jUg5rsn�k��B �; �v��;��c#��q×�Gqty!w5y� e*�wUsB�¥x®��ww�w��u/x s^uS� y!~@�Q R x®w/�v�qQ ; � #ny!w@��$u/x@s^u���qZ*@�T*UyW{£{)�q�/qzw����^q¼xºw��vqz�N���Ô�B Á�vu�q'9Uy%�¥q�¥qz����y%�,; ��b� ;��c=

f qnuUy5A>q}yW{®�vqty%�:��¥qzqzwK�Ê�����v�dyÌw@�y c�>�N� y!�¥x®��w@�$#5; ��b� ; yÌw@�; ��b� ; �$u/x@svu'� y!~Z�^u�qW�¥qz���3�B Q%R x®w/�v�<Q%R<=�μw����vu�qz�\��qB{�{®�B /w��B�$w��v�dy!w@�Ê c���7� y!�¥x®��wSx����^u�qkbjUgB��i3j@������g"�@k�l5rsn�k��B ªy�~l�!x®w1�»� y!~�>D%; � ; � �v�¢�z*U9@�¥qz���r�B �;C*@��x®w ( �vu�q� �yB�Sx£{£x@y!�W�/qVdUw/x®�¥x®��w<`\H�� � ¿! � O�; � � �#" ×O�`���~$ � �% 0H��0�cÀ.=Æ��¥x£{£{��T�����G���vqÕ�v�dy!w@�Ê c���7� y!�¥x®��w@��y!�^q �vu�q×*�~�~Uqz�5#�y!w@��{º�B��qz�5#�9U�p*�w@� ��~Uqz�dyÌ�v��������w5y�~Uy!�v�¥x@yW{£{)������/qz�^q5���¥qz�5=pr� ( �v�%*�w@�"�%*��Kx®w/�N*/x®�¥x)A�q�*�w@�/qz���¥�dyÌw@�>xºw ( �B ¼�v�dy!w@�y ����N�Õy!�¥x®��w@��x®w5�^qz�N�����! Ô�^u�q wUy!�7*��dyW{qVv��

�vqzw@��x®��w��B Ïy"~l�!x®w1��� y!~ � y%��xs�ÕsV*@�¥�v�p� y!�N�"x®w��v��~U�Ì{º� ( �@�¼x�� �v�"x®w.A>x®�vqPsB�>w: e*@��x®��w�= ?��Sx��×��*Us^u9Uqz�^�vqz���^��9lq ( x®w>��x®�vuPyGs^{®�.�z*��vqZ��~lqz�dy!�v�>�5#@��#My%�Ô��w�q'&���~Uy!�By%�>x ( �£9Uqtszy!*@�¥qS�v�dy!w@�y ����N�Õy!�¥x®��w@��szy!w9Uq���x£{��>{)� �Sx��T9lqzuUy3A�q5�b=�?�w& �y�sB�5#r~��v�%9UyB9/{)�)�^u�q�9lq5�¥�<�/qVdUw/xº�§xº�>w%�B «"¸.¯%|!6�x�� ( x)A�qzw x®w%�vqz�N���¼�B �v�dyÌw@�y c�>�N� y!�¥x®��w@��~®�"�y=Áp�u�qz�vqÔxs��yB� ~/{ºqt�vsB��~Uq» ������Sx��T9UqzuUy3A>x®���\9UqtszyB*@�¥q»�q��%9@�¥qz�NA�q��vuUyÌ�nxI ]; y!w@�; � yÌ�vq¢�§qz���:�B �(�qB{®q"�Gqzw1�V��qty�s^u�#1�^u�qz�vq�qVv/x��¥�$��w/{)�)(+*��>x��¥�¥x®wUsB�, c*�wUsB�¥x®��w@�,�>D%; � ; � sB�%� ~Uy!�vq5��v� � Q,*U� � è �^�dy!w@�y ����N� yÌ�¥x®��w@�,; ��b� ; � =¼pF� y>svu/x®q"A�qGy!w:���vq5�T*/{®���¼�B nx®w/�vqz�vq5�¥�Z��q'��*@�§�ÏsB��w@�§�v�dyWx®w�vu�q��v�By!w@�y ����N� y!�§xº�>w@�"=

� w�qÕszy!w5qzw:*U�Gqz�dyÌ�vqGyÕ{®��w ( #8w���w���qVv�uUyB*@�¥�¥x)A�q {£x��¥�S�B �v�By!w@�y ����N� y!�§xº�>wP~��^��~Uqz�v�§xºq5�$#�2BÃ�³:Ã�� xs��vyWx�� �v��9Uq%DsB��w/�v�dy�sB�§x�A>q xI � `\H��>� � � `��.-qVv�~Uy!w@��x)A�q xI � `\H��>�0/ � `��.-�G��w��>�v��w�q xI W_u�w` x)�G~/{£x®q5�Z_>H�� �w`\H��1-y!w/�¥x)�G��w����^��w�q xI W_u�w` x)�G~/{£x®q5�Z_>H��32w`\H��1-

¤

Page 7: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

*�w/x��%*�qB{)� ( qzw�qz�dyÌ�vq5� xI W_>H�� �P`�H���x)�G~/{£x®q5� � _��<`��VH�����_qH���#*�w/x®��w"~��vq5�¥qz�NA>x®w ( xI � _�¾<`���H�� �P_qH���¾�`\H��1-/����¥�dy!9/{ºq xI W`\H�� �w`�#

�����yW{£{]_>FN` ��;>=f q �%9@�¥qz�7A�q"�vuUy!��s^{º�:�T*��vq%#Z�W#Ôx����G��w��>�v��w�qPyÌw@��qVv�~Uy!w@��x)A�q'-��$u/x£{ºq � xs��sB��w/�v�dy�sB�¥x)A�q"y!w@�

�¥�dy!9/{ºq%#09U*��$w����t�G��w��>�v��w�q%=W� w�qzq5��w����,9lq�*�w/xs�p*�qB{)� ( qzw�qz�By!�vq5�b#09U*����vu�q��^q5�T*/{®���$�! ª�vu/x���~Uy!~Uqz�y!�vq:�vq5�¥�v�§x sB�^q5���v�$qVvUyB�G~/{®q5���$u�qz�^qnx®�8x��"=�É3�B�qz�3#�y!w@��*�~�~Uqz�5#B9l�%*�w@�K��~Uqz�By!�v�����ry!�vqyÌw1�¥x)�G�>w����v��w�q'-y!w@�Õ�vu�qKwUy!�N*��dy�{ÃqVv��vqzw@��x®��w��B }yS~U�!x®w/�\ c*�wUsB�¥x®��w�x��»*�w/xº�>w ~��vq5�¥qz�7A�x®w ( y!w@���G�>w����v��w�q%=

?Ð @��qn�vq ( y!���Z� y%�Fy»� y!~�~/x®w ( �/qVdUw�q5�K��wK�vu�qs^{®�.�z*��vq��¥~Uy>sBq � ;>FV����#!y%���z* (%( q5�¥�vq5��9.��rx ( *��^q�QU#�vu�qzw���q�� y3��9Uq ( xºw��^�ZqVv�~/{º�>�vq����vu�qz�:~��v��~Uqz�^�¥x®q5�$y%�N�¥��s^x@y!�vq5�×��x®�vu��]=������vq"� �.�¥�8x����vu�qZ�%*�q5�§�¥x®��w�#

;

� ;>FV���

;��

� ;��cFV���s�

�� �� �1�

�rx ( *��vq�Q DY���vq ( y!���/q5��yp�$ySs^{º�:�T*��vq��§~Uy�sBqZ�v�By!w@�y ����N� y!�§xº�>w�$u�qzw xs�Ô�vu�q��>x@y ( �ByB� �B Y�rx ( *��^q�QGsB�%�×��*��By!�¥x)A�q��

����� � ���������� ������������� �����! #"��$���&%' "�()����������

μw.���v�dy!w@�y ����N�Õy!�¥x®��w � ;�FV��� ���� � ; � F�� � ���vuUy!�t� y!~@��s^{®�.�§q5�&�¥qz�����B Â; x®w/�v���vu�qGs^{®�.�¥q5�&�¥qz�V�$�B ;��\���%*/{��%wUy!�N*��ByW{£{���9Uq"szyW{£{ºq5� y&�p�)nbl"�UÑ �v�dy!w@�y ����N�Õy!�¥x®��wS9.��y!wUy�{º� ( �5�^�)�v��~l�!{®� ( x@szyW{£{)����~lqzw� y!~@�$=p�uUyÌ��x��"#��Pxs�¼s^{®�.�¥q5� xI W` s^{®�.�¥q5�+xºw � ;>FV���Éx�� ~/{�x®q5��`�H�� x��¼s^{º�:�¥q5� xºw � ; H��0F�� � ��=W?�w"�vu�q5�¥q�/qVdUw/x®�¥x®��w@�×�qÕ�dy�s^x®�¥{)�%y%�N�T*U� q �vuUyÌ�µ;>H�� x��Gs^{®�.�¥q5� x®wP;��W�Ôxº�^u%�vq5�¥~UqtsB� �v�q�1�c=)p�u/x��Sqzw@�T*��^q5�"#9:��É3q"�<� y��%=Î�U#À�vuUy!�$�vu�qK�vqB{@y!�¥x)A�qSs^{º�:�T*��vqS�B W� � �Ôxº�^uP�^q5�¥~UqtsB�¼�v��;>H��Pxs�¼sB��w: ����N� y!9/{ºq���x®�vu��vu�qs^{®�.�T*��vqK��w�; � =���0oSoqj)��©c§ *)´ � ; F��¡� ��b� � ;���FV���¶�Z/)6Á�|%-0|%°c|%-@2�¯%-0}�«3¬I|B682V}BÖW°¶¸.23-

_qH��0H�� ��� _qH���H��0F �@_u�P;

��� �!�#"�$ * »S¢Z�W���t���t���®¤¥�£��»!¨),54+*9-3,54 6L4+*l½ * ¬��B¨������/¤¥��,54I6��£�}¤¥­£�t���d°S�z�1°,* �£�}¤¥­£�t���B°�¨1,54+* 4I6.- -F,54I6L4+*U½b

È���w��>�v��w/x@s^x®�Ê�Sy!~�~UqtyÌ���8�v�t9Uq�yt9Uy%�<x sÔ~��v��~Uqz�^�Ê�%=�?��}szy!w�9Uq,*@�¥q5�×�v���%9��dyWx®w<�¥q"A�qz�ByW{1x®w/�vqz�vq5�¥�§xºw (�vq5�T*/{®���$= � szszy%��x®��wUyW{£{)�%#���qayW{��¥���$y!w/�Ïy×��qty^ � ����N���B }x®w:A�qz���¥q��G��w��>�v��w/x@s^x®�Ê��-3�vuUy!��x��"#���q'�ÔyÌw1�

Ì

Page 8: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

�v��9UqZy!9/{ºq��^�×yp�N�¥qz�v���vuUy!���vu�qz�^q�qVv/x��¥���$y!�:{®qty%�¥����w�q�~��^qz�Xx��Õy ( q�¥qz��y�{s�§�µ�^y!�¥x��y c��x®w ( �vu�q¼x®wUs^{)*@��x®��w~��v��~lqz�v�T�%=�Î �v�dy!w@�y ����N�Õy!�¥x®��w�; ��b� ;��lx��,�vyWx�� �v�<9Uq���Ó�Ó��®i o>n�kbn@g"nLk�� xI � y:�Éxº�Ôxs�»�G��w��>�v��w�q%#b/eÃs2�á_u�w` x)�G~/{£x®q5�Z_>H�� �w`�H��]#�y!w@�� 9b��_qH�� �w`\H��Õx)�G~/{£x®q5���^u�qz�vq�qVv1x��¥�V�,`���T*Usvu��^uUy!�,`��%H����P`\H��"y!w@� _ �w`��%=

?��Ôxs��qty%��x£{)���¥u��B�$w��vuUyÌ�5D

���0oSoqj)��© ����25° d ��0� d � . 2�¯%-0²<°c4T¯%-U6¶´8|p4�Á�¯%°c/¶|%-�Ã, ¯�-)*)´ � _£��`×��H�� �P_>H��×�<`�H��LÖW°¶¸.23-��P/s6¢Á�|%-0|%°c|%-02�Ã,�. -)*)´ � _£¾�`×��H�� �P_>H��×¾<`�H��LÖW°¶¸.23-��P/s6¢+${%{U254Á�|%-0|%°c|%-02

��� �!�#"�$% � ( , -3E5�£¢K¦�­£���^�!,F7 E�:3,�½�8�t�����dËW¬��v�!��­£»!¨ ,54+*O7 EL4 *`: % ,37 E ( 4+*J:<,54+*U¨W�£¢Z¦�­£»!�£���L,54 *M-FEL4+*U½% « (+D �v�>,2-FE �£¢Z¦>­�»!�£����,��8E�:3Ea½3¾n >�v�U¨1,54+*��`EL4 *�: % ,��`E ( 4+*8:0EL4 *×��¢K¦�­£»!���>�Z,54+*M-FEL4 *l½¾M�¼�v���<�z«>­��£�� a¬>¦�¦1�^¡}¢Z�W���t���t���®¤¥�£��»!¨z­£�v�>,54+*�-0EL4 *l½ D �v�>E��f:<,��8EZ½r¾n ��v��E��C4+*J: % ,��8E ( 4 *�:,54 *��`EL4+*Q: EO4+* ���1°8, -3E��z½>b

Î �v�By!w@�y ����N� y!�§xº�>w � ;>FV��� ���� � ;��cF�� ���3x��\�vyWx��S�^�9Uqt�Bn�k@g5rÐk��bn���l�xI �`\H���s^{®�.�¥q5�×x®w � ;�H��0F��1�s�x)�G~/{£x®q5�t`�H��\H����P`\H��

�:��w1�§xºw:*/x®�T�Gx����v�dy%�>x®�¥x®��wUyW{£{)�q�/qVdUw�q5� x®w �^qz�N�����B n~��v��~lqz�v�¥x®q5���B ª�^u�q�x®w.A>qz���¥q�Õy!~�#Uy%�:x®wB�vu�qx®w.A>qz���¥q:x)� y ( q��B Fs^{º�:�¥q5���¥qz���rx��ns^{®�.�¥q5�!�U=}pÔu/xs�nyÌ~�~Uqty!�����>x �Fqz�vqzw/�5=n|�qty%�>x£{)�%#:` � H�� Í x��:y�sB�!{£{®qtsB�¥x®��w�B ,�¥qz����¿5` ��;0� `\H�� ��` ��À:=ZpF��9UqÕsB��w1�§xºw:*��%*@�¼q"A�qz�7�q�¥qz�Z` O>`��cH�� Í w�qzq5�"w����Z9lq×s^{®�.�§q5��x®w; T*@�¥�Z9Uqtszy!*@�¥q�` � x��Zs^{®�.�¥q5��x®w ; � -]9U*��'�$u�qzw�q"A�qz�'` OS` � H�� Í x®���Zs^{®�.�T*��^q<��*@�¥�9lq y%�t��qB{£{Ð=���>�y!wÕq5�%*/x)A!yW{®qzw1�\ ����N��*/{@y!�¥x®��w�#Ì{®qz��` � 9lqÏs^{®�.�¥q5� x®w�; � y!w@�×{®qz�\` � H�� Í 9Uq�~Uy!�^�¥x@yW{£{�� �����/qz�vq5�×9.�x®wUs^{)*@��x®��w�=\?c �� x���sB�>w1�¥x®w:*��%*@�"#��^u�qzw�` �Õy3v1x)� y�{Fx®w�` � H�� Í�x)�G~/{£x®q5�t` x��¼s^{®�.�¥q5�Õx®w>;>=pr��*�w@�/qz�V�¥�dy!w@� �vu�qÕ�vqty%�§��w> ����S�vu/x����/qVdUw/x®�¥x®��w�#�sB��w@��x��/qz�G�^u�q���x)�G~/{®q��v�dy!w@�y ����N�Õy!�¥x®��w&�%�B

�rx ( *��vq��'�$u/x@svu�� y!~@��y¼{£x®w�qty!�$�>���/qz����w+��~U�!x®w/���:��w/�v�ay�{£x®w�qty!�$�����/qz�:��w�QZ~l�!x®w1�V�"#�y%�8x®w@�>x@szy!�vq5�9:� �vu�q�y%�N�<x ( wU�Gqzw1�V���v�S�vu�q¼�¥x ( u1�3=}p�u/x��,�"sB�%*/{���9Uq��vq ( y!���/q5��y%��y!w�qz~/x®�v�%� q��B ªy zsB��w/�¥x®w.*��p*@���( �dyÌ~�u5�v�By!w@�y ����N� y!�§xº�>w�= p�u�q ( �dyÌ~�u)��w½¿�E0��F�� �IÀ x��Gs^{®�.�§q5�S��x®�vu5�^q5�¥~UqtsB�G�^��yÌw.�"�B ��^u�q+s^{®�.�T*��^q��~lqz�dy!�v���V���vuUy!�,��qKw����N� yW{£{)� y%�N�§� s^x@y!�vq'��x®�vuq�z*Usvu"y�sV� s^{£x@s ( �By!~�u@�"#U�$u/x£{®q�¿�E��3À�O ¿�E � F�� � À.H�� Í xs�s^{®�.�¥q5����x®�vu �vq5�¥~UqtsB���v�Zw���w�q¼�B F�vu�q"��= �n{®qty!�§{��%# �q¼szy!w�& �}�^q5�%*/x®�vq�q"A�qz�7�a~��^qz�Xx��Õy ( q¼�v�9lqÏs^{®�.�¥q5�b=f)q�9UqB{£x®q"A�qÕ�vu�q<�/qVdUw/x®�¥x®��w5�! zsB��w/�¥x®w.*/x®�T� �Õ�^uUy!�Z��qZuUy3A�q ( x)A�qzw)szy!~��N*��vq5�¼�^u�qZx®w/�N*/x®�¥x)A�qÕw����¥x®��w�B n�vu�qZsB��wUsBqz~���sB���v�vqtsB�§{��%=:p�u�q�¥qtsB��w@� �G���¥x)A�yÌ�¥x®��w�x��,É3q"�×� y�Q =Î�U#%9lqB{®���'=

Page 9: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

a’ c’

a b c

f{ac}.f = {a’c’}

{a}.f = {a’}{b}.f = {a’}{c}.f = {c’}{ab}.f = {a’}

{bc}.f = {a’c’}{abc}.f = {a’c’}

�rx ( *��vqa�UD�Î zsB�>w1�¥x®w:*��%*@���S�^�dy!w@�y ����N� yÌ�¥x®��w

���0oSoqj)��©�� *)´ � ;>FV��� ��0� � ; � F�� � �W/s6W|%-@°c|BÖb+"{p{®254\Á�|%-0|%°c|%-@2\¯%-0}Z«�|p-@°c/¶-@+:|%+%6 0 /¶°¶¸�;>H�� «5¬I|B6"2�}/¶- � ;���F�� �¶�¢°¶¸:25-

`�H���H�� �w`\H��@H�� � F �@`h� d

��� �!�#"�$ EO4+*�- EL4+* 4I6�-@½ D �v��� -H:�EL4+* 4I6�-]- �+4 *l½�\!�£�1¤¥� *Õ�£�}�W�����1¨�������¬/¤� Õ�� /�z���f4+*5:�� -�½��n�z©%«!»¬�¦�¦/�v¡¼¢Z�W���t���t���®¤¥�£��»!¨���� �� E -� � ��¬/¤� ��� 1�z��� � 4+* :��f4+* :GEO4+* 4I6.-�½� l�£�1��­�­£»!¨/���£�1¤¥�,*��£��¤¥�W�����£��¬>�t¬��B¨� � 4I6O4+*`:<EO4+* 4I6.-�½ * ¬��d¨W���£�1¤§�ZEG-�� � ¨^EL4I6+-�� � 4I68¨����1°¼«!»�¢K�t���W���W���®¤¥�£��»�¨ EO4I6L4+*�-�� � 4I6L4+*J:<EO4+* 4 6�-X½>b

$nbi5nb���sj@i�� �b©8*)´ � ;>F��¡� ��b� � ; � F�� � �W/)6\|%-@°c|BÖ�+"{%{U254\Á�|%-@|p°c|%-@2$Ö]«�|p-@°c/¶-@+:|%+%6VÖ�¯%-@}Z«3¬I|B682V}Z°¶¸.23-_qH���H�� �P_>H��@H�� � F �@_u�P;

�$u/x@s^u5q5�¥�ByB9/{£xs�§u�q5�<�T*:�+s^x®qzw/�×sB�>w@�>xº�§xº�>w@�Z �������y!w@�&� �v� 9Uq�sB�%�<��*��dy!�§x�A>qa�^�dy!w@�y ����N� yÌ�¥x®��w@��x®w�rx ( *��vqQU=

��� � #"��$���&%' "�()���������� $%�� "������� ����. "��

� �By!~�u �vu�qz���N��~��v�BA�x��/q5� y �§x s^u {º�/y%���B a�v�By!w@�y ����N� y!�§xº�>w@�Õ��A>qz���>x��vsB�vqz�^q �¥~Uy>sBq5�"#¼~Uy!�v�¥x@sV*/{@y!�¥{)�( �dyÌ~�u u��%�G�p�G���v~�u/x��T���$=\?�w"�vu/x����§qtsB�¥x®��w>�q��/q5�vsB�¥x)9Uq ( �By!~�u u��%� �%�G���v~�u/x��T����x®w"�vqz�N���Ô�B }�vu�q~��v��~lqz�v�¥x®q5����q$uUy3A�q�T*@�¥���/qVdUw�q5�b= � 8~Uy!�v�¥x@sV*/{@y!�:x®w1�vqz�^q5�¥�W��x£{£{�9Uq¼�vu�q$�v�By!w@�y ����N� y!�§xº�>wa~��^��~Uqz�v�§xºq5��B ��G��w����^��w/x@s^xº�T�%#UsB�>w1�¥x®w:*/x®�Ê� yÌw@��s^{º�:�T*��vq%=

ÉÃqz���C� ��� F! ×��= � w�q�� y3� �^q ( y!���ÕqBx®�vu�qz�¼�vu�qZw��U�/q5�"#l~U�!x®w/���"#l���,A�qz�^�¥x@sBq5�"# � #��B n�vu�q ( �dy!~�uy%�É��w�q'&���*�w/x)A�qz�V�¥q%#U; -1�>�}��w�q,�Õy5�S�v�^qty!�n�vu�q¼q5� ( q��¥qz�5#" �#1y%��;>=Y�À���}�^u/xs�:~Uy!~lqz�5#:��q�y%�N�T*U� q$�vu�q ����N�Gqz�5=,ÉÃqz�#� � � ��� � F! � ��=»ÎÒ e*�wUsB�§xº�>w � D � � � � xs�¼szyW{£{®q5�)y ��i3j@Ó ¦ ¦ nLoqnLoqnbi�Ó ¦ r�l!o�$'#�/qzw����vq5�%� ��0� � � #/xI &(' Þvß�å*)®é,+�ä7Þ1å�á�çÎÝMæWÜ.-�èzçÎåXçÎäBè�ß�Ü0/zâzçÎß�Ü¥ÝFÞ8ãtß�Ü�ç�ß$ÞvîBÜnâtèWætÜ¥ß21�Þ®ädßlÜTédÜ¥ß�ê�Ü¥ætîBÜ3çÎè�354£÷@î�ä�ß�ÜnÞvâWå�átäBß�ÝMæWänètäBålç�ßã!äBÝ�Üå�ázçÎÝ8ß�Ü0/zâzçÎß�ÜTß�Ü¥èzå¥÷

Page 10: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

� y:� ��� F U��O yÌw@� � H��&¼�% 0H�� x)�G~/{)� ��� H��@F @H��L��O �� 9b� ��� � F � �WO � x)�G~/{£x®q5�¼�vu�qz�vqKqVv1x��¥�V� ��� F U��O h�T*Us^u��vuUy!�

� H�� � � � yÌw@�) @H�� �% � =p�u�q��v�By!w@�y ����N� y!�§xº�>w �B W�rx ( *��vqZ�Kx��¼y ( �dyÌ~�u�u��%�G�%�G�>�v~�u/x��T��=

Æ!x®wUsBq�x®�rx��8w����nuUy!�����v�¢�§u���� �vuUy!�8�v�dyÌw@��x®�¥x)A�qs^{®�.�T*��^q$��wayÌwZq5� ( q,�¥qz�� x���*�w/x��%*�qB{)� ( qzw�qz�By!�vq5�xI ÉyÌw@�Õ��w/{)�GxI � xs��y�sV��s^{£x@sB#@��q�y%�N�T*U�Gq � x���~Uy!�v�¥x@yW{£{)�Õ�����/qz�vq5��9:� �Z#Uy!w@�×��qÏyp�N�T*U�Gq��vuUyÌ����xs���w�q��B

`�H���� � ¿ � � � � @F <O�`�À`�H���� � ¿�� � ���UF �O�`�À � Q:�`�H��� � ¿ � � Í � � � � F Í F � O�`�À.H

�$u/x@s^u��q�sB�!{£{®qtsB�¥x)A�qB{)�PszyW{£{YÓLjUg ¦ �p�)nblB��i5�Ul%=np�u�qtdU�V�¥���Ê���Sy!�vq�/�}%2V¯%¬!��~lqz�dy!�v�>���"#/�vu�q�{ yÌ�v�vqz�:x��$y!w/¶-@°c254V15¯p¬���~Uqz�By!�v���5=�5p�u�qGs^{®�.�T*��vqG�! ��rx ( *��vq�� � y:�nx����%9��dyWx®w�q5� 9.�"y!~�~/{)��x®w ( � � �^� �vu�q ( �By!~�u �B �rx ( *��vqG� � 9b��=

���"y�lB� � �bi5j@Ó ¦ � �B �h��q��Gqty!w y!w.���§qz� ��� � � �Ôxº�^uPq5� ( q��¥qz�� � ���\#3�vuUyÌ�$x��Zy'´"+:¬�¬�T*U9 ( �By!~�u�=���0oSoqj)��©�����25°��&D�� � � � . 2�¯<³%4T¯V{@¸ ¸.|%Á�|%Á�|%4Ð{@¸./s68Á'Ö�¯p-@}�¬I25°�� . 2<¯%-0²t{®¯p°¶¸q«5¬I|B6"+:4Ê2Bà *)´� ��/)6«3¬­|!682V}�/¶-�� �W°¶¸.23- � � � ��H�� Í /)6«3¬­|!682V}�/¶-���Ã��� �!�#"�$��É�d�t°Ì��­£»������¼�£¢Z¦�­£�£�v��� 4+*����#4 *l½�z�/���R6�� $ D �v� � -�«1��¤§­��W���d°×���"! -������� 1��� � -$#"�,-�¨%� -&��� -U�£¢K¦�­£»'� -$#"�,-�½ D �v� �'#(�,- 4+**)$+f-�� -U���1°­£�v�,�-���>½J\!�£�1¤¥� * �£���K ��t¢K�t¢Z�W¡�¦� >�Î��¢.� 4 */� - �#4+*U½ * �B¤v�z¬����0� - ����­��§�@�$¤¥­£�t���B°�¨1� 4+*/#�� - �£¢Z¦�­£»!�£�����#"�,-B4 **)$+:�����,-�4 **)$+:���n­£�¥�X�ª¤¥­£�W���d°�½�z�/���R632L$54}�£¡���¬1�z­£­£»��®°!�v�!���®¤v��­�½�z�/���3616T$ D �v�7�,-F«/�Z¤¥­£�t���d°Õ©n¡��B½J686n¨U�z�/°G­£�v�,� � ��-��,-B4+*&)3+]½¼�X�:9S�£�Ô�K¦/�t�£�!���t���Z¦/�z�� l¨U��¬1¤� ��� 1����;� 9��<���� >�v�=9#4+*Õ���:�t� ��¦1�z�� (� 4 *=�>914+*?�<�14+* ���@! -@½�\!�£�1¤¥�,� -M�£��616 ¤¥­£�t���B°�¨$914+*@#?�,-3�£¢Z¦�­£»!�£���9A#(�,-�4+*&)3+}©n ��®¤� a�£�8�� ��^¡��¥�@�W¡����z­£����¤¥­£�t���d°K©n¡��B½O686n½>b

f q uUy3A�q�*@�§q5� �vu�q w��>�dy!�¥x®��w�#t�hD�� � � �$�v� q"�G~�uUy%��x)Çzq)�vuUyÌ��� �^q ( y!���/q5� y%�Õy ( �dy!~�uu��%�G�p�G���v~�u/x��T��x���<x�� ~/{��)y× c*�wUsB�¥x®��w&� yÌ~�~/xºw ( ��w�qSw��®�/q��¥qz�¼x®w1�v� yÌw����vu�qz� -Ãxº�¼x��×-@|%°8�vqtyW{£{)�)y�v�dyÌw@�y c�>�N� y!�¥x®��w�=8p�u�q<-@¯p°c+.4T¯%¬�2$º�°c23-U6"/�|%-0#!x®w���u/x s^u�`\H�� � ¿! 0��O � �B� �#" ×O�`<��~ '�0�% 0H��0�cÀZ� y^ �q5�x®��yS�v�By!w@�y ����N� y!�§xº�>w �B WQ � �^��Q � 4 =���0oSoqj)��©�� ��25°@�>D�� � � � . 2t¯Z³%4T¯V{@¸<¸:|%Á�|%Á�|%4c{0¸./)6"Á'ÖW¯%-@}�¬I25°0� . 2Z¯%-@²�{U¯%°¶¸�«3¬­|!68+:4T2�Ã8��¸:2-@¯p°c+.4T¯%¬�2$º�°c23-U6"/�|%- � ��b� � � /s6¢«V|%-0°c/�-0+.|%+p65Ã��� �!�#"�$B�É�d�t°Ì��­£»!¨��z�!»G�1����¬�¡¥�z­F�¥Â����v�����£�W� *�¦�¡��v���v¡��t�v�¼¬����£�W���d¨l���S«!» A ½ A �£��¬�¦�¦/�v¡$¢Z�W���t���t���W½ D �^�,�«/������¬�«��t¡¥�z¦�  �z��! ��¬/¤�  �� 1��� �54+* �£�}¤¥­£�t���B°�½Z\Ì���.->�54+* 4+*&)3+]¨>©n ��®¤� G�£�}�� >�$���v�����r��­£­�¦1�W���!��� �;#=CDFE è�ì ëHG í�ä�å�áWÜÞ^âtå�átäBßnàvÞTÜàÜÎÜ¥æSå�átÜÉçÎèzå�Ü¥ßcédÞTÜ3ädã!Ü¥ß�Þ^å�ädßnå�áWÜ'IKJMLON�PRQ5SOTMUVUtäBã!Ü¥ß�Þvå�äBßFW�çÎè×ì ózí�ì Xyí¶ä!çÎå8çÎÝÁàvÞzÜàÜÎÜ<æGÞ^è(JMY[ZMP�Y

IRJMLON�PKQFäBã!Ü<ß�Þ^å�äBߥ÷

�5Ë

Page 11: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

��¬/¤� K�� 1��� � 4+*�#(�54+*l½ * » D �v¢K¢a� A ½���¨ �94+* 4+**)$+8���n¤¥­£�t���d°�½�8�W�����dËW¬��^����­£»�¨O�2- �54I6+-��54+* 4+*&)3+Á�£¢Z¦>­��£�v��54+*8-��54I6L4+*8-��94 *l¹!�����BËt¬/�z­£�£��»¼�@�t­£­£�z©n�d½Lb

f u/x£{®q��^u�q�wUy!�7*��dyW{UqVv��vqzw@��x®��w��B Áy!w:� ( �dy!~�uGu��p�G�%�G���^~�u/xs�z� ����*@�¥��9Uq�sB��w/�¥x®w.*��%*@�$#!x®��w�qzq5�w�����9Uq�s^{º�:�¥q5� yp�n�vu�q�sB�p*�w1�vqz�:qVvÀy!�G~/{®q��B ]�rx ( *��vq � x£{£{)*@�¥�v�dyÌ�vq5�"=}|�qtyp�>x�{)�%#��^u�q��¥qz�,¿BE.G�� À�x��s^{®�.�§q5�

a

b

c

d

e

fa’

b’

c’

d’

�rx ( *��^q � D � �By!~�u�u��%�G�%� ���v~�u/x��T��#U��#��vuUy!�Ôxs�Ôw�����s^{®�.�¥q5�x®w�;���x®�vu��vq5�¥~lqtsB�$�v��� � #:9U*���x®���:x)� y ( q¿�E0�)G ���0�)À¼x���w����$s^{®�.�¥q5�+xºw�;��09UqtszyB*@�§q � ��O>¿BE'�)G ���0�)À:H�� � =pÔu�qZ�v��~l�!{®� ( x@szyW{W�¥���v�3#��b#l�B y ~Uy!�v�¥x@yW{£{)� ���V�/qz�vq5���¥qz�¼~��v�BA>xs�/q5��yÌw����vu�qz�¼qVvÀyB� ~/{ºq%=t?��$x��¼qty%�T�

�v�w�¥u��B� �vuUy!��� xs� w����Õw����N� yW{£{)��s^{®�.�¥q5�½��x®�vu �vq5�§~UqtsB� �^�5qBx®�vu�qz�>���������5 -Z9U*����vuUy!� x®�Õxs�sB��w/�¥x®w.*��p*@�"#F��w/�v�@#8y!w@�>*�~�~lqz��� ��w����v��w�q%=�?�w@�/qzq5�b#���x®wUsBq�`\H�� � �h¿ � � ��� @F >OS`�À:#F�vu�q� �y�sB��vuUy!�»`�H�� �]H����P`\H�UH��8�]#��>�$q5�%*/x)A!yW{®qzw1�¥{)�"�vuUy!� � � Sx)�G~/{£x®q5� � H� � 0H� x����B c�^qzw �dy^ >qzw��v�<9Uq�x®����/qVdUw/x®�¥x®��w�=

?��Kxs�×w����<�T*��v~��¥x���x®w ( �vuUy!� ( �dy!~�u u��%�G�p�G���v~�u/x��T���Sy!w@� �^��~U�!{®� ( x szy�{»�§���v���Sy!�vq�sB��w/�¥x®w.*��p*@�"=B*@�¥�¼y%�:x®wPy!wUy�{��U��x��"#Àx®��x��$wUy!�7*��dyW{F�v��dU���§���/qVdUw�qay!w@���§�N*@�:����qB{£{®�c9UqzuUy3A�q5���v�dyÌw@�y c�>�N� y!�¥x®��w@�$=

����� "����."�� "��.���."�������� #"��$���&%' "�( �.���� ���

XW�p*Uy!�¥x®��w � �B�,�/qVdUw�q5�¼~Uy!�v�¥x@yW{n�����/qz�V� �� y!w@� � � 4 ��w � ;>F��¡�ÔyÌw@� � ;���F�� �¶��^q5�¥~UqtsB�¥x)A�qB{)�%=ZÎ�v�dyÌw@�y c�>�N� y!�¥x®��w���x��Z�vyWx����v��9Uq�nbi�ÑL�Ui�Ó]i3�Ul"�Ui %�rck'��x­ \_ ��&` x)�G~/{£x®q5�Z_>H��8� � 4 `\H�� �����yW{£{_>FN` � ;>=½?������%*/{��w9lq u���~lq5���^uUy!� s^{®�.�¥q5�b#¼sB��w1�§xºw:*��%*@� �v�dy!w@�Ê c���7� y!�¥x®��w@�'���%*/{���9Uq �>���/qz�~��vq5�¥qz�7A�x®w ( =w��*��5#n�vu/x��Sw�qzq5� w��>�<9Uq��v�7*�q%= �}��w@�<xs�/qz���rx ( *��vq�ØU#8x®ww�$u/x@s^u%�vu�q�w��®�/q5�×E5y!w@�SG�B ��^u�q ( �dy!~�u%��w �vu�qÕ{®qV ��<9U���^uw� y!~%��w/�v�qE � ��w%�vu�qÕ�¥x ( u/�5=S?��Kx��Gw����SuUy!�V� �v�>A�qz�¥xI e� �vuUy!�<�

c’

d’

a c

d

b

a’f

�rx ( *��vqØUD � �dy!~�u�u��%�G�p�G���v~�u/x��T��#U��#��vuUyÌ��x���w����$���V�/qz�$~��vq5�¥qz�NA>x®w (x��K��w1�^�@#�*�~�~lqz�<�G��w����^��w/x@sB#ªs^{®�.�§q5�5y!w@� sB��w/�¥x®w.*��p*@��Ôxº�^u)�vq5�¥~lqtsB�a�^�q���]= �W*���� x��Kw����Z�>���/qz�~��vq5�¥qz�7A�x®w ( �= �5= �5=<���]#L9UqtszyB*@�¥q xI �_ �£¿ �3À y!w@�&` �h¿�G���� À.#3�vu�qzw)�vqtyp�>x�{)�S_ � � ` 9UqtszyB*@�§q`Ò�<_qH��&� ¿ �3À¢� _ �w`\H���#U��qz�,_>H���¼� � 4 `\H�� 9UqtszyB*@�¥q'`�H��<�<_>H��0H�� �b� ¿�E0��� �)À�¼�½¿ � �sÀZ�P_qH��]=

?�wq�rx ( *��vq�ØU#b��x���y ( �dy!~�u�u��p�G�%�G���^~�u/xs�z��#Uu�qzwUsBq�*�w/x®��w"~��vq5�¥qz�7A�x®w ( =�Æ�� q"A�qzw"y%�U�>x®w ( �vu/x��~��v��~lqz�v�T���v� sB��w/�¥x®w.*/x®�T�%#Fs^{®�.�T*��vq%#3�>w1�v��y!w@� *�~�~Uqz�'�G��w����^��w/x@s^xº�T� xs��x®w@�T*:��s^xºqzw/�Z�^� qzw@�T*��^qG�vuUy!�� 9UqK�����/qz�$~��vq5�§qz�NA�x®w ( =\��*��5#

���

Page 12: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

¥�¦ �:n�i3�@o ��©�c *s´ � ;>FV��� ��b� � ; � FV� � �/s6«5¬I|B6"2�}!Ö�«V|%-@°c/¶-@+:|%+p6�Ö\|%-@°c|BÖ,+${%{®234�Á�|p-@|%°c|%-02<¯%-0}�/�- ¹°c25476"2�«3°c/�|%-µ{�4T2"6"254V15/¶-.³!ÖW°¶¸.25-��w/s6|%4T}%254�{b4Ê2$68234�13/�-:³.Ã

��� �!�#"�$ D �v�`, ��� EZ¨r���+Ea79,54I6G- , - EO4I68½ * �B¤v�z¬�����*"�£�¼���!���v¡����d¤¥���£�W�P¦>¡��v���v¡��!�£���1¨8©8�Z 1�B�W�¬������>� D �^¢Z¢a� A ½ & ¨>EO4+*57�,54 * 4I6�-J- EL4+*57 ,54 6L4+*�: % E_7�,54I6 ( 4+* -.,54 *l½�Ø:�1°�¨n«!» D �v¢Z¢S� A ½ P ¨,54+*�-3EO4I6L4+*�-3EO4+* 4 6�-�½3�t¡L,54+* ������EL4+*U½ b

�É{º�:�T*��vq y!w@� sB��w1�§xºw:*/x®�T�%#�9:�P�^u�q"���¥qB{)A�q5�ZyÌ�vqSx®w@�T*:�+s^x®qzw/�a�^��qzw@�T*��vqÕ�vuUy!�ZyÕ�v�dyÌw@�y c�>�N� y!�¥x®��wx������V�/qz��~��vq5�¥qz�NA>x®w ( -�9U*��K��w�q��Sx ( u1��u��>~UqG�vuUyÌ�������/qz��~��vq5�¥qz�7A�x®w ( �^�dy!w@�y ����N� yÌ�¥x®��w@�$y!�vqGs^{®�.�¥q5�b#sB��w/�¥x®w.*��p*@�"#Uy!w@��sB�%�<��*��vqt��x®�vuq�\#�y%�:x®w>�rx ( *��vq�QU=���w: c�>�v�N*�wUy!�vqB{)�%#U��qZszy!w���w/{)� ~��^��A>q

���0oSoqj)��©�h *)´�; ��b� ; � /)6Z|%4T}%234\{�4T2"6"254V15/¶-.³!ÖY°¶¸:25-, ¯�- ´/)6«3¬I|B682V} , {�4T|%15/¶}%2V}�;>H��w/)6«3¬I|B682V}�/�-�;�� -BÖ,�. - _qH��WH�� �w_>H��0H�� � ÖH�@_u�P; Ã

��� �!�#"�$% � (+D �v� �%«/�$¤¥­£�t���B°S�£� % �Õ¨ 6 ( ¨!�� ��^�5, � � � �£¢Z¦>­�»!�£����,54+*<� ��� �+4+*l¨!���`,54+*G�£�}¤¥­£�W���d°�½% « ( U�£¡����d¨^,54I6L4+*�-3,54+* 4I6�-U«/�d¤v��¬�����, � � ,54I6��£¢Z¦>­�»!�£����,54I6L4 * � � � ,54 *�t¡d¨^,54+*X78,54 6L4+* 4I6.- -F,54I6L4+*8-F,54+* 4I6.-�½>b

��*��5#>xI W��qZy%�U��T*@�¥�$�vu�qK~��v��~Uqz�^�Ê� �B Y� ��w����v��w/x@s^x®�T����q��%9��ByWx®w

$nbi5nb���sj@i�� �b©�� *)´ � ;>FV��� ��0� � ; � FV� � �¢/s6Á�|%-@|p°c|%-@2�¯%-0}�|%4T}%234\{�4T2$68234�13/�-:³<°¶¸.23-_qH���H�� �P_>H��@H����cF �@_u�P;

��� �!�#"�$ * »Õ¢Z�t�>�t���W���®¤¥�£��»�¨#, -�,54I6 ��¢K¦�­£�£�v�>,54+*3-�,54I6L4+*U½J\Ì�a«/�d¤v��¬����,*��£�$¤¥­£�t���d° % D �v¢Z¢S� A ½ ( ¨,54+* 4 6�-!-3,54I6L4 * 4I6�- :<,54 6L4+*l½>b?�w yW{£{��vu�q��vq5�z*/{º�V�G�B ��vu/x����¥qtsB�¥x®��w�#��G��w����v�>w/x s^x®�T�%uUy%��9lqzqzw y3 >q"�5~��v�>~Uqz�v�T�%=w?��Sx�� y3 >x®w@�%�B ��qB{£{º�¶ ����N� q5�<9lqzuUy5A>x®���}�^uUy!�W�¥qzq"���ÉwUy!�N*��dyW{U�^��qVv ~lqtsB�5=W��*��W� y �x®w ( x®�\�¥�ZsBqzw1�^�dyW{@� y3��9Uq,���v��w ( =p�u�q× e*�w@��y!�Gqzw1�ByW{}x��N�T*�q��^q"� yWx®w@� V�$u�qzw xs�'_>H���H��½�h_qH��@H�� � � � #�9U*��Kxºw �vu�qÕw�qVv �<�¥qtsB�§xº�>w ��qy!~�~��v�/y�svuÕx®�$�By!�vu�qz���>x �Fqz�vqzw/�¥{)�%=

� �� ��� ������Z���

�8qz�vuUy!~@�Õ�^u�qq��x)�G~/{®q5�¥���v�dy!w@�y ����N�Õy!�¥x®��w��^uUy!�+szyÌw 9lq)y!~�~/{£xºq5� �v�%y%s^{®�.�T*��vq&�¥~Uy�sBq�x���T*@�¥���vu�q�vq"�G�BA!yW{U�B F��w�q%#��>�W�G���^q%#��B 3x®���n~l�!x®w1�V�"=�f)q�szy�{�{3�vu�q"� �/qB{®qz�¥x®��w@�$=���*��W9lqV c�>�vq¢�/qVdUw/x®w ( �/qB{®qz�¥x®��w@��vu�q"���§qB{�A>q5��x®��x��¼sB��w.A>qzw/xºqzw/�¼�v�<�/q"A�qB{®��~PyGsB�>wUsBqz~����B W�/qz~Uqzw@�/qzwUsBq%=

�5Q

Page 13: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

� ��� � � � �.��������� �

f)q�vy3�Õ�vuUy!�,M�x���ÑL�®Ó��0k�Ñ��0k@gZ�>w<J���x®�vu��vq5�¥~lqtsB���^�<` xI M<¼O `�H�� 9U*�� M'O � `Ò¾�¿�JbÀ%�VH��P=

|�qty%�>x£{)��J ¼O�`�H�� qB{��¥q � ` ¾ ¿�JbÀ%�VH��>�P`\H���=���qzwUsBq%#U9.� yÌw1�¥x®��qVvUsvuUyÌw ( q,J&¼O � ` ¾�¿�MpÀ%��H��W=f qS{®qz��`\H � �/qzw����vqÕ�vu�q��§qz�Z�B �yW{£{��T*Us^u MÕ�vuUyÌ�ay!�vq��/qz~Uqzw@�/qzw/�G��w J �Ôxº�^u5�vq5�§~UqtsB�S�v��`�=

�n{®qty!�¥{)�%#Ãx­ �JP¼O `�H��%�vu�qzw�J&O `�H � =Sp�u/x��"#Fy!w@�����vu�qz��<x�� ~/{ºq ~��v��~Uqz�^�¥x®q5���B }�vu�q5�§qµ�/qz~lqzw@�/qzwUsBq�¥qz���$#Uy!�vqZ�T*U�<� yÌ�¥x)Çzq5�Õx®w�D

���0oSoqj ��©c§ *�- ¯�+.-0/�±3+.23¬­²'³%25-0254T¯%°c2V}BÖ�¯%-@°c/¶Á�¯%°c4T|%/�}�«3¬I|B68+:4T2'6K{U¯%«�2$Ö � ;>F��¡�NÖ, ¯�-`�.J�F _>H�� �<_>H � � Ù�Ã,�. -,J�O�_>H��½/¶Á,{b¬­/¶2"6,_>H � Z� ÙµÃ, «�-Z_qH � ¼� Ù /¶Á»{�¬I/�2$6YJ O�_>H � Ã, }�-_qH�� � ¿VJbÀ�/¶Á»{�¬I/�2$6

,�� -_ �� _£¾�¿�JbÀpÖ,�� - . |%°¶¸�_ ¯%-@}'_£¾ ¿�JbÀ�¯p4Ê2׫5¬I|B6"2�}.Ã

, 2�-,J&¼O�_>H��½¯%-0}_ ¼� � _£¾�¿VJbÀ�/ ´¯%-@}�|%-0¬I²�/ ´ " M�O�_>H � F M<¼� J�Ö , /cÃ)2BÃ`� _>H � � /PQ -.Ã, ´ -M�O�_>H � F�M×¼� J /�Á»{�¬I/¶2"6 Ù � _qH � � �w_>H � Ã, ³�-Z_qH � ¢��_qH���H �

��� �!�#"�$% � ( ¯ % ¤ ( * »S°!�¥Ö1���£�����W�U½

% ° ( 8�t¡��W­£­º��¡�»¼�z�2 �¬��/°��z¢K�v�!�<�z­ 8�z�t�^¡��£����¾n ��v�W¡��v¢ & ½ A % � ( ½% � (� #�,54I6K��¢K¦�­£�£�v�!, � ��, �� � � % «!»� 8¾ & ½ AC( ¨B�z�1°Ô���£�1¤¥�L, � � , �� � � ¨ ,54 6 �� �����0% , �� ��� ( 4I6�t¡5��� # % ,��� � � ( 4I6 � � #5,54I6 ���1°�� : � ½

% � (+* »S�z�!������»�¢K¢Z�v��¡�»!¨ �) #�,54 ���W½% � ( � #�,54 ���¼�Ñ�M�z�/°¼�t��­£»¼�Î��� #5,54I6 ���1°�� #5, �� � � 4 �������1°��£����¬>¡��Z�Ñ�M���1°��W��­£»$�Ñ���7#�,54I6L4 ���/½>b

f u/x£{®q&��q&�/qVdUw�q �/qz~Uqzw@�/qzwUsBqS��x®�vu��vq5�§~UqtsB���v��y!�79/xº�^�dy!�N�w`�#,9:� ÉÃq"�<� y%�U=®� � ( ���q)szy!w�vq5�¥�^�¥x@sB��x®���v�Gs^{®�.�¥q5� �¥qz���"=¡?�w �^u/xs��szy%�¥q%#��vu�q��¼�¶ �y�sB�v�>�$�vqB{@y!�¥x®��w��B Â~�Ø5�8szy!w�9UqK�vq5�¥�dy!�^q5��y%�

M ����J��� "! � M�O�`�H�� y!w@�"�^u�qBxº�Sp�u�qz���vq"� Q =Î�U#3�vuUy!� � ;>F��¡��xs�Ky>«�|p-@152$ºµ³p2�|pÁ�23°c4�² � /eÃs2�õ*�w/xs�p*�qB{)� ( qzw�qz�dyÌ�vq5�0�$xI �y!w@���w/{)� x­ ¼�vu�q �^qB{ yÌ�¥x®��w � � x��Gy ~Uy!�v�¥x@yW{$���V�/qz�Z ����GyW{£{�s^{®�.�§q5�S`�#� ��!{£{®���t�Zqtyp��x£{��%=>?�w@�/qzq5�b#sB�>w.A�qVv( qz�%� qz�v�¥x®q5�8~��v�BA�x��/q�y» �qz�v�¥x£{®qZ�¥�%*��dsBq��B Fy!w1�§x��Õy!�v�v�!x��Ss^{®�.�T*��vqt�¥~Uy�sBq5�"=�Î ��x)�G~/{®q¢Ø¼~l�!x®w1� ( qz�%�Gqz�^�N�x���x£{£{)*@�¥�v�dyÌ�vq5� xºw&�rx ( *��vq�¤ � y:�V=�?�����s^{º�:�T*��vqK{@y!�v�¥x@sBq%#0�$u�qz�vqZ�^u�qas^{®�.�T*��vqK��~Uqz�By!�v����� x����vu�qasB�>w.A�qVvu:*/{�{Z�>~Uqz�dy!�^���5#:x����¥u��B�$w x����rx ( *��vq&¤ � 9b��= g����¥x@sBq)�vuUy!��M½O�¿�E.G��3À:H � �u¿�E:G3À.H � yÌw@� ��O¿�E:MpÀ.H � � ¿�E:G"M%À:H � � ¿ �TJbÀ.=

�t�

Page 14: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

a

cp

b

q

ab

a b

abp

abcpqbcpapq

bcpqacpqabcq

abc abq acp acq bpq bcq cpq

ap ac aq bp bc bq cp pq cq

p c q

Ø

(a)

(b)

abpq abcp

�rx ( *��vq�¤UD�Î sB�>w.A�qVv ( qz�%� qz�v�N� � ;>F��¡�}y!w@� ������� ���

�:��A>qz�¥x®w ( �vqB{@y!�¥x®��w@�¥u/x®~@��y!�^q¼x�� ~U���v�By!w1�Ôxºw&�>x��vsB�vqz�^q��¥�v�7*UsB�N*��vq5�"#�2BÃ�³:Ã�p�u�qz���vq"� �%=�Q =�?�w"y%�U�>x®��¥x®��w��v� �vu�qZsB�BA�qz�¥x®w ( ~��v��~lqz�v�¥x®q5��qVv ~��vq5�7�¥q5�Õx®wqÉÃq"�<� yÕ�U=®� � �0�ny!w@� � qB��#:�q�uUy3A�q���0oSoqj ��© ���|%4Z¯%¬¶¬U_u�P; ÖW/ ´WJ ¼O�_>H��½°¶¸.25-�_�¾�_>H � «V|%15234N6 � _�¾<_qH�� � � ¿�JbÀ®Ã

��� �!�#"�$ ¾n >���8�£�Á�!�£¡���¬1�z­£­£»���¤¥�t¡��t­£­®�z¡�»¼�z� D �v¢K¢a� P ½ & % ° ( ���£�1¤¥��, �`,54 � � : % % ,��`,54 � � ( � ��� ( 4 � � b¼qz~lqzw@�/qzwUsBqSx����>x®�vqtsB�§{��"�vqB{@y!�^q5���v�Õ�vu�q�{@y!�^�¥x@sBqµ�§�v�N*UsB�N*��vq��/q5�vsB�¥x)9Uq5�Pxºw)p�u�qz�>�vq"� �p=�Ø��$u/x@s^u

y%�N�§qz�v���¼xI Z`�H�� � � a,H�� �^u�qzwS c���Sqty�s^uS`�OÏ~à`\H���FN`\H��b��^u�qz�vq qVv/x��¥���Gy *�w/x��p*�q>a OÏ~Ia,H���F"a,H��0��T*Us^u �vuUyÌ��`Ò¾ �h� aZ=Z�hxºw��vu/x��$�^u�qz���vq"� xs��y��/qz~lqzw@�/qzwUsBq��¥qz�5=��nyÌ�vu@�� ��v�%� �vu�q�{®�B��qz��{®qV c�¼�v�*�~�~Uqz���¥x ( u1�$sB��w@�§�¥x®�N*��vqZ�/qz~Uqzw@�/qzwUsBq��§qz���"=�¼qz~Uqzw@�/qzwUsBq%#H��#�y!w@� ( qzw�qz�dy!�v�>���"# ��# yÌ�vq�x®w1�^qz�v�T��x®w�q5�9:� �vu�qt ��!{£{®�B��x®w ( {®q"�<� y =���0oSoqj ��©�����|%4Z¯%¬¶¬%J>¼O�_>H���F J�O � _£¾ ¿�JbÀ%��H��q�w_>H���¾�¿VJbÀ®Ã

��� �!�#"�$ �n�d�W°!�£­�» % , � ��� ( 4 -,54I68¨����£�1¤§� �� # ,54I6Á½ D �v�B¨���# % , � � � ( 4 F½ % , � � � � � � ( 4I6�:% , �� ��� ( 4 6r½��n�^�1¤¥�n«!»�¬����®ËW¬��F�t�^���v¡<�����£�t��¦�¡��W¦1�v¡���»�¨ % , �� � � ( 4 5- % , �� ��� ( 7 % , �� � � �� � � ( :<, �� � ��£¢Z¦�­£»!�£�����v�£�� ��^¡ �f: � �t¡�� #Q,�½\!�£�1¤¥� �) #�,54I6 � % ,�� ��� ( 4 -�,54I6n½H\!�¼�@¡��t¢��� ��$�t«>���v¡��t�z���£�W�a�z«/�z�t�W¨ � # % ,�� � � ( 4 F½ l�£�1�z­£­£»�¨�«�» D �v¢K¢a� & ½ V#% � ( ¨ % ,��� ��� ( 4 � � � -F,54 F½>bpÔu�qGx)�G~/{£x@szy!�¥x®��w@�S�! ��vu/x���{ºq"�×� y"szy!w 9lq��§qzqzw)x®wP�rx ( *��vq"� � y:�V=�Æ!x®wUsBq>¿ �!À.H�� �½� ¿BE ���!À��

� �

Page 15: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

¿ ���!À.H�� � #�¿ ���BÀ:H��Ò� ¿ �!À.= ¿ ���BÀ.H����µ� ¿�G3À+yÌw@� � ¿ ���BÀZ¾&¿�G3Àp��H�� ��¿�G��!À�� ¿ ���!À.H��>¾&¿�G3À:=���*��5#�vu�q��^yB�GqG~��v�>~Uqz�v�¥x®q5��u��!{��)q"A�qzw �$u�qzw)�vu�q��/qz~lqzw@�/qzwUsV� �§qz��x���w����Sy���x®w ( {®qz�v��w�=����>��qVvÀyB� ~/{ºq%#� ¿ ���!À\¾�¿ �UÀp��H��>� ¿ ���BÀZ�½¿ ���!À.H���¾�¿ �UÀ.=

� � � ��� � �.��� ������) " �����&% �"�()������ �

����y l3rck'���s��Ó�nbrck@gPÑL�U�)�:g5r)nLkY#�� #��! �y s^{®�.�T*��vq&�¥~Uy�sBq � ;>F��¡��#���q��Gqty!w y"�v�dyÌw@�y c�>�N� y!�¥x®��w� ;>FV��������0� � ; � F�� � ��#U��u�qz�vq; � � ; � ¿�JbÀSy!w@��� � �½���� 4 y!w@�� x����/qVdUw�q5� 9:��D

`�H�� � � ` xI &J&¼O�``Ò¾ � ` � ¿�JbÀp��H � � ¿�JbÀ �>�vu�qz�N��x��¥q%#

� �:�

f)q¼�%9@�¥qz�NA>q%#1�^uUy!� � x���y��qB{£{®�K�/qVdUw�q5�b#U�>w1�v�� e*�wUsB�§xº�>w�#Uy!w@� �vuUy!�� �����w����dyÌ�¥x®��wUyW{Ãs^{@y!�§xº�T�<��qt� y3��%�Sx®���vu�qZ�T*U9@�vsB�¥x®~���J��$u�qzwÕx®�:xs��s^{®qty!�\ ��v�%� �vu�q�sB��w1�^qVv ���$uUy!�}~l�!x®w1�Ôxs��9lqBxºw ( qB{�x)�Sx®wUy!�^q5�Õx®w��vu�q�/qB{®qz�¥x®��w�=

���0oSoqj ��©Ò` � ¿�JbÀh� `\H�Å � `�H�� � ¿VJbÀZ�P`\H��WH�Å F �.J O�;>FN`C�P;

��� �!�#"�$)�X� � #5E"�� ��Á¡��v��¬>­��l�£���v�����v�!���®�z­£­£»���¡��£�!�®�z­�½ D �v� � #5EZ½�Ù��3Ö1¡����l�t«����v¡��W�Á�� 1�z���v�£�� ��v¡HEO4I6Z¤§�z�t�v¡��d¨z�W¡�£�U¤¥�z�t�^¡��d°�«!»�¨ EO4I6 � � � ¨^��� EO4I6L4 � ��:0EL4I6 � ��� ½ \Ì���/¤¥� � #QES¨ EO4�� ��:0E � % E � � � ( 4 ��� � � � ½ * ¬>�d¨B���£�1¤¥�% E � � � ( 4 ���X: �[= � # % E � � � ( 4I6 � � #QEL4I6 � -3EO4I68¨!�£�F�X�t­£­£�z©n�F�� 1���>EO4�� �0- EO4I6 � � � :<EO4I6L4 � ��½b

�:��A>qz�¥x®w ( �vqB{@y!�¥x®��w@�§u/xº~@�axºw:A��!{)A>x®w ( �vu�q��/qB{®qz�vq5� qB{®q"�Gqzw/�¢J%y!�^qGx)�G~l���v�dy!w/�5= pÔu�qGx)�G~Uy�sB�S�B �/qB{®qz�¥x®��w�x���s^{®qty!�¥{)���vq"A>qtyW{®q5��9:� �vu�q� c�Ì{�{®�B��x®w ( �/qVdUw/xº�§xº�>wq��u/x s^u�x���q5�%*/x)A!yW{®qzw1���v� � �®�y!w@���$u/x@s^ux��$qtyp��x£{���q5�§�dyB9/{£x��¥u�q5� *@��x®w ( p�u�qz�>�vq"� �%=�QSy!w@��ÉÃq"�<� y%�¼�U=®��y!w@���U=�QU=

`\H�� �������` xI J&¼O�`` � ¿�JbÀ xI P` sB��A>qz����` � ¿VJbÀ.#����\` � ¿�JbÀSsB��A>qz����``Ò¾ � ` � ¿�JbÀp��H � � ¿�JbÀ ���vu�qz�7��x��¥q%#

?c �` x��}s^{®�.�¥q5�Õy!w@�ZJ�O�`�#��vu�qzw qBxº�^u�qz�YJ�O `�H�����u�qzwUsBq�` sB�BA�qz����` � ¿VJbÀ�����J>¼O `�H��>�¥�Z` � ¿VJbÀsB�BA�qz����`�=�?�w"y!w:� szy%�¥q%#U` s^{®�.�¥q5�+x)�G~/{£xºq5�t`\H�� �P` � ¿�JbÀ.=

� ��� � " 2� �." � ���.� $% � �.��� ���� �

?�w��vu/x����¥qtsB�¥x®��w�#\��q qVv�~/{®���vq��vu�q �v�By!w@�y ����N� y!�§xº�>w%~��v��~Uqz�^�¥x®q5�G�B ��/qB{®qz�¥x®��w�=Ò����� qVvÀyB� ~/{ºq%#���w�q���%*/{�����x��¥u �^uUy!�,�/qB{ºqz�§xº�>w@��� ��qz�vqZ� ��w����v��w�qZ�¥�G�^u�q��vq5�T*/{®�����B �Æ�qtsB�¥x®��wqQU= �ÏsB�p*/{s� 9UqZy!~�~/{£x®q5��-9U*����vu�q"�)y!�vqSw����3= �}��w@��x��/qz�K�vu�q<��x®w ( {®q ~l�!x®w1���/qB{ºqz�§xº�>w�� �B ,�rx ( *��vq�Ì.=�$qz�vq%#L��q�*@�§q×sB�>w.A�qVv~Uy!�vu�s^{®�.�z*��vq%#,� = p�u�q��T*U9@�§qz���G�! � ;>FV� �ZuUy3A�q�9lqzqzw ~UyÌ�v�¥x®�¥x®��w�q5� x®w/�v�)~��vqz�Xx)� y ( qq�T*U9@�§qz���y%��x®w@�>x@szy!�vq5� 9.�>�/���v�vq5�+{£xºw�q5�$=Gp�u�q��T*U9@�¥qz�V�t` �B � ;>F�����$uUy3A�q�9Uqzqzw �����/qz�vq5� 9:� � �B���v�� ����N�� � ��� ��� � =�X8{®q"�Gqzw/�����B � ;��cFV��� �8uUy5A>q��vu�qZ�vyB� q${@yB9lqB{s�$#@9U*���~��¥x)�Gq5�b#UyÌw@� y!�^q¢��x)�Sx£{@y!�¥{)�����V�/qz�vq5�b=

�5Ø

Page 16: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

a bc

d

χd

abcd

abdabc bcd

ab cd

a cb d

bc bd

ad

acd

ac

Ø Ø

a’ b’ c’

a’b’ b’c’

a’ b’ c’

a’b’c’

a’c’

�rx ( *��^q�Ì.D�ÎÏ��x®w ( {®qZ~U�Ìxºw/�Z�/qB{ºqz�§xº�>w�# � #��vuUy!�:x���w����,�G��w��>�v��w�q|�qty%�>x£{)�%#�¿�E��UÀ�� ¿BE ��� À.#:9U*��¿BE � À.H�� � ¿�E0��G �sÀ�¼� ¿�E0��� �)À�� ¿BE ��� À.H�� =\f)qZszy!w�#lu��B��q"A�qz�5#�~��v�BA�qyS�vq5�§�v�¥x@sB�vq5�× ����N� �B ��G��w��>�v��w/x@s^x®�Ê�%=

���0oSoqj ��©�����25° � ;>FV��� ����b� � ;��¶F�� ��� . 2¯�6"/�-:³%¬I2\{U|%/�-0°W}%23¬I25°c/¶|%-, ¯�-�*)´,` Í ¯%-0}` � ¯%4T2�«3¬I|B682V}BÖ�°¶¸.25- � ` Í ��` � ��H�� �P` Í H�� �<` � H�� Ã

��25°b` Í �w` � Ã,�. -�*s´¢23/�°¶¸.234,` Í |%4»` � /s6«5¬I|B6"2V}BÖY°¶¸:25-�` Í H�� �w` � H � Ã, «�-�*s´�` Í H�� �P` � H���ÖW°¶¸:25-�` Í H�� �w` � H � Ã��� �!�#"�$� ����\!�£�1¤§�RE + ���1°<E��Õ�z¡��+¤¥­£�W���d°�¨ E + 7 E��G¢�¬>���Z«/���z�S©Á�^­�­�½��X� � #_E + % �t¡JE��Õ�t¡8E + 7 E�� ( �� ��v�

E + 4 � � :3E + � ��� ½�8�t�����dËW¬��v�!��­£»!¨ % E + 78E � ( 4 � �X:0E + 7 E � � � � :0E + 4 � � 7JE � 4 � �1½� ��� D �v�fE + «/��¤¥­£�t���d°�½8�X� �) #5E + �� ���¡��v��¬�­£�n�@�W­�­£�z©n�8�£¢Z¢��d°!�®�����v­£»!½��:�� ��v¡�©n�£���t¨/«!» D �v¢K¢a� P ½ V ¨^E + 4 � � :

E + � ��� ½H\!�`E + 4 � ��:<E + � ��� -FE � � ��� -3E � 4 � �/½D �v�]E � «/�}¤¥­£�t���d°�½3�X� �� #�E � ¨t�� ��n¡��^��¬�­£�8���8�z�����£�$�£¢Z¢Z�B°!�®�z���W½ * » D �v¢K¢a� P ½ V ¨ E + 4 � �X-3E + 4I6 � � � ½* ¬��>E + -3E � �£¢K¦�­£���^�]E + 4 6�-�E � 4I65:<E � ¨!���`E + 4 � �X-3E � 4I6 � � � :<E � 4 � ��½

� ��RE + � E � #� EL4 6 � EL4 �¿½3�X� �) #�E � ¨!�� ��^� �� #QE + ¨����1°8E + 4 � ��:<E + -3E � :0E � 4 � ��X� � #FE � ¨3«�¬�� � #0E + ¨U�� ��v� � #0EO4 5�z�/°+E � � ��� ¤§�z�t�v¡�� E � ½ 8�W�����BËt¬>�v�!��­£» E + 4 � �5: E + -E � � ��� :<E � 4 � �>½D �v� � # E + �£¢Z¦>­�»!�£��� � #�E � ½��X� �� # EO4 F¨��� >�v� E + � � E + � � � ���1°5E � � � E � � � � ½�¾n !¬��d¨

�5¤

Page 17: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

E + 4 � � :3E + � ��� -3E�� � � � :3E�� 4 � � ½lÙ) ��£­£�3�Ñ� � #QEL4 8¨B�� ��v�XE + 4 � � :<E + � % E + � � � ( 4 � � � � � :E + �����= � # % E + � � � ( 4 � ��� � #5E + 4I6 � � � � -FE�� �� �X= � # % E�� � � � ( 4 � ��� � #5E�� 4I6 � � � � :E�� 4 � � ¨!«/�d¤v��¬����XE + 4I65:<E�� 4I68½>b

� 9@�§qz�NA�qS�vuUy!��xI �9U�>�vu>` Í yÌw@��` � y!�vqas^{®�.�§q5�b#F�vu�qzw&É3q"�<�Õy��U=�Ø � 9b�Éxs��y���x)�G~/{®q�sB���v�!{£{@y!�N���B �vu�q�~��vqtsBq5�>x®w ( ~Uy!�^� � y:�}y!w@��É3q"�×� y<QU=�Q =pÔu��vqzq�� ���vq��/qB{®qz�¥x®��w@�"#�yW{£{��/qVdUw�q5� ��w �vu�q�Ø ~U�!x®w/� ( �dy!~�u �B ��rx ( *��vq � #���x£{�{¼u�qB{º~P�/q"A>qB{º�>~

�vu�q<�¥qzw@�¥qS�B }�^u/xs�¼�^�dy!w@�y ����N� yÌ�¥x®��w�=\Î ( yWx®w�#lxºw yW{£{Észy%�§q5�,��q�*@�¥qGsB��w:A�qVv ~Uy!�vu"s^{º�:�T*��vq%#]� =�p�u�q�/qB{®qz�¥x®��w�# ���V#/�B ��rx ( *��vq��¼x��:�vu�q��<x�� ~/{ºq5�§�5=�Î�{�{]�¥qz�V�ny!�vq,� yÌ~�~Uq5� ��w1�^���vu�q"���¥qB{)A�q5�:���n�v�K��w�q$�vu�q"�

ab

c

d

e

χ c

abcde

abcd abce

aceabd

bcde

bcebcd

bdbcacab

a b c d

be

e

dececd

cdebde

ade

acde abde

abeacd

aead

abc

ac

Ø

Ø

a’b’ d’

e’a’d’e’

a’d’

b’d’e’

a’b’ a’e’ b’d’ b’e’

a’ b’ d’ e’

a’b’d’e’

d’e’

a’b’e’a’b’d’

�rx ( *��vqZ�UD}p�u�q�<xºw ( {ºqS~l�!x®w1���/qB{®qz�¥x®��w�# ���$y!~�~/{£x®q5� �^�a�^u�qas^{®�.�T*��vq��¥~Uy�sBq��B W�rx ( *��vq �sB�BA�qz� � ���ay!�^q sB�BA�qz�vq5�>9:�@�V=�g$�>�¥x@sBq u��B��q"A�qz�5#r�vuUy!� � y:��#�¿BE �����BÀ.H � � ��¿�E � � � � � À �£¿BE � G � � � � � À��¿�E:G���� �!À.H����V#��§� É3q"�<� y �U= � szy!w�w����<9lqq�¥�^�vqzw ( �vu�qzw�q5�b#$y!w@� � 9b�Z�vuUy!�G�^u�q s^{º�:�¥q5�P�¥qz� ¿�E ���!ÀÕxs�� y!~�~lq5����w/�v��¿�E � � � À'�$u/x@svu xs�¼y ( qzw�qz�By!�v���:x®w � ;>FV� �N#U9U*��¼s^{º�:�¥q5� xºw � ; � FV� � �N=���0oSoqj ��©�� Õ�/¶-.³p¬I2,{U|%/¶-@°\}%25¬I23°c/�|%- 6 � ; F��¡� � ��b� � ; � FV� � �¯%4T2<«3¬­|!682V}.Ã�*8Ãs2�õ/ ´t` /s6�«3¬­|!682V} 0 4�°KÃ��ÖW°¶¸.23-�`\H�� /)6«3¬I|B682V} 0 4V°KÃ,� �KÃ

��� �!�#"�$ D �v�>E�«/�$¤¥­£�t���B°S©n¡��f68½3�X� � #QEZ¨>�� ��^�a«!» D �v¢K¢a� & ½ % � ( E�:0EL4 � ���£�n¤¥­£�t���B°S©n¡��B½]6T= �n½�X� � #5EK¨��� >�v�G«/�d¤v�z¬>���`E �£�¤¥­£�t���d°�¨/�v�£�� >�v¡fE�¤§�z�t�v¡��fE � ���C% � #5EO4 ( ¨��W¡��B¶@Å¥È�zÈv´§¸^²�½8���a�^���� ��v¡�¤v�z���t¨EO4 � � :3E � � � ½lØ}�/°Z���£�1¤¥��EL4 � � :0E � ��� :0E07�� -c¨^EL4 � � �£�}¤¥­£�t���d°K©n¡��B½O6>= � )� � � :�6.-X½>b

�:���v�!{£{@y!�N���U=IÌZsB���v�^q5�¥~U��w@�U�Ô�v��É3q"�<�Õy<QU=®�¼qVvUsBqz~����vuUyÌ��x®���/�1q5�Ôw�����x®w.A>�1 �qZ�G��w��>�v��w/x@s^x®�Ê�%=

�BÌ

Page 18: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

$nbi5nb���sj@i�� �L©�c *)´ � ;>FV��� � ��0� � ; � FV� � �¢/s6¯×68/¶-.³p¬­2Â{®|%/¶-@°�}%25¬I23°c/�|%->°¶¸.23-`�H � H�� � �w`\H���H��

��� �!�#"�$ * » D �v¢Z¢S� P ½ V ¨OEL4 � �-2EO4I6L4 � �1½ EO4I6����S¤¥­£�t���d°�¨n��� «/�d¤v�z¬>��� � �����S¤¥­£�t���d° %BD �v¢K¢a� P ½�� (EO4 � � 4I6�-!-3EO4I6L4 � �1½>bpÔu�q��/qB{®qz�¥x®��w�# � ! #n�B ¢�rx ( *��vq � x��Sy 9/xº�×�G���vq�sB�%�G~/{®qVv�= ���>�aqVvUyB�G~/{®q%#\¿BE ���BÀ�� y!~@�K��w/�v�

ab

c

d

e

χ e

abcde

abcd abce

aceabd

bcde

bcebcd

bdbcacab

a b c d

be

e

dececd

cdebde

ade

acde abde

abeacd

aead

abc

ac

Ø Ø

a’b’ d’

c’

a’c’d’

a’d’

a’b’c’

a’b’ a’c’ b’c’ b’d’ c’d’

a’ b’ c’ d’

a’b’d’ b’c’d’

a’b’c’d’

�rx ( *��vqS�UDnp�u�q��<xºw ( {ºqK~U�!x®w/�¢�/qB{®qz�¥x®��w�# � ! y!~�~/{£x®q5� �^�G�vu�qZs^{®�.�T*��vq��¥~Uy�sBqK�B Y�rx ( *��vq �¿�E0��� � �0�)À�9lqtszyB*@�¥q ��O½¿BE � À.H ��!5= � 9@�¥qz�NA�qG�^u�qG�v�!{®qG�B ��/qz~lqzw@�/qzwUsV� �¥qz�V� -F�vu�q"��x®w@�T*��vqÕ�vuUy!�K�vu/x���/qB{®qz�¥x®��w x���sB��w/�¥x®w.*��p*@�"=Ï�����ÕqVvÀy!�G~/{®q%#¿BE.G��!Àq� yÌ~@�G��w/�v��¿�E0�­G ��� �sÀ&�$u/x@svu�x���y s^{º�:�¥q5� �¥qz� x®w� ; � F�� � ��=�Î�w@�×�$u/x£{®q¿�E:G��BÀ�x��nw�����s^{º�:�¥q5�Sx®w � ;>F�� �Fx®����s^{®�.�T*��vqZ¿BE.G����!ÀZ� ¿�E:G��BÀ.H�� yW{��¥��Õy!~@���w/�v��¿�E � G � � � À.=

���0oSoqj ��©�h Õ�/¶-.³p¬I2�{®|p/�-0°}%23¬­23°c/�|p-U6VÖ � ;>F��¡� ������ � ;��cF�� �)�7Öµ¯p4Ê2>«V|%-@°c/¶-@+:|%+p6$à *8Ãs2�à / ´<`\H�� /)6«5¬I|B6"2V}BÖY°¶¸:25-�`�H��\H�� �P`\H�� Ã��� �!�#"�$ D �v�>E#-�«/��¤¥­£�t���d°K��� % � - � 6 - ( �z�/°Z­£�v�>EL4 � � :<E -�½3Ù��$�z����¬�¢K�fE��£�n���W�}¤¥­£�t���B°�¨��v­£���$�� ���¡��v��¬�­£��@�W­�­£�z©n�F��¡��£�!�®�z­£­£»�½�X� �� #QE �� >�v�5EO4 � ��:0E�:<E -�¨!����«!» D �v¢Z¢S� & ½ % « ( ¨^E �£�}¤¥­£�t���d°K©n¡��d½L68½D �^� � #�Ea¨z��� EL4 � � :<E � % E � ��� ( 4 � � � ��� :<E - ©n ��®¤� ����8¤¥­£�t���B°¼©n¡��d½]6 - ½�8�t�����dËW¬��v�!��­£»�«!» D �v¢Z¢S�& ½ % « ( ¨ E � % E � ��� ( 4 � � � � � ¢�¬����:«1��¤¥­£�t���d°G©n¡��d½�6"�z�/°G«!»S¾n ��v�W¡��v¢ & ½ A^% � ( ¨#E � % E � � � ( 4 ���¢�¬����F«1��¤¥­£�t���d°K©n¡��d½]6����Á©8�v­£­�½ * �d¤v��¬�����EO4I6 7 E � % E � ��� ( 4 � � � �£�n¤¥­£�t���B°�¨^EO4I6�-FE � % E � ��� ( 4 � � ½

�t�

Page 19: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

�S�W¡��v�z�W�v¡d¨^EL4 69:0E � % E � � � ( 4 � � «/�d¤v��¬������ � #�E � % E � ��� ( 4 � � �v�£�� ��v¡�� #5E%�W¡ � # % E � ��� ( 4 � ��£¢Z¦�­£»!�£��� � #5EL4 6 % «1�B¤v�z¬���� � #QE ( ½3¾n !¬��d¨#EO4I6L4 � � :0E � % E � � � ( 4 � � � ��� :0E -Lb

���0oSoqj ��©�� *)´ � ; F��¡� ����b� � ;���FV���¶�Z/)6¯×68/¶-.³p¬I2\{®|p/�-0°W}%23¬­23°c/�|p-UÖW°¶¸.23-`�H���H�� �w`\H�� H�� �

��� �!�#"�$ \!�£�1¤§� � � ¢S�z¦�� % � � 6 ( �t�!��� % � - � 6�- ( ¨:©n ��v¡�� � - : � � � � �z�1°<6.-J: 6f= � ) � � ¨}�� ��v¡���¥Â��£����� E��9- ����¬1¤�  �� /�z�XE �8: EO4 � � 4I6.-X¨F�z�1° ���£�1¤¥� � � �£��¤¥�W�����£��¬>�t¬��B¨3©Á�K¢a�B»G�z����¬�¢K�`E ������¤¥­£�t���d°�½8�t�>���dËW¬��v�!��­�»!¨^E�� 4 � � :<E � � � � :0EL4 � � 4 6�-X½3¾n �¬>�d¨^EO4 � � -FE�� � ��� �£¢Z¦�­£»!�£���fE -FE��:©n ��®¤� ����n¤¥­£�t���d°�½\!�/¨^EO4I6 -3E � ���1°8EO4I6L4 � �X-3E � 4 � ��:<EO4 � � 4I6.-X½>b

¥�¦ �:n�i3�@o ��©c§��8*)´ � ;>FV��� � ��b� � ;���FV���¶�Z/)6Z¯�6"/�-:³%¬I2\{U|%/�-0°W}%23¬I25°c/¶|%-UÖ�°¶¸.25-`�H���H�� �P`\H�� H�� �

��� �!�#"�$ % Ù��$�t«>���v¡��t���� /�z�fEL4 � � 4 6 - -�EO4I6L4 � �Z«!» 8�t¡��t­£­®�z¡�» P ½��>¨��v�W�v� �� ��t¬>�t G©8�$©n�£­£­U���W�}¬������� ��£�}�£��� >�$¦�¡��!���<½ ( �X�HE �£�}¤¥­£�W���d°�¨>�� ��^�G«!» D �^¢Z¢a� P ½ ��EO4I6L4 � � �£�}¤¥­£�t���d°�¨����`EO4 � � 4I6 - :0EL4I6>4 � � ½�8�W�����dËW¬��^����­£»�¨©8�Ô������¬�¢Z��E �£�Á���W�}¤¥­£�t���d°S�£� % � � 6 ( ½��3�£�� ��v¡ � #�EO4 Õ�t¡n���W�d½�X� �� #QEL4 6 �� ��^�5EO4I6L4 � � :<EO4I65:<EO4I6>= � )� � � :0EL4 � � 4 6�-X¨�����©8�$�z����¬�¢K� � #�EO4I68½�X� � #[EL4 F¨F�� >�v�3EO4I6 �£��¤¥�z�t�^¡��d°�«!» EO4I6 � � � �z�1° �v�£�� ��v¡ � #[E �t¡XE � � � ¤¥�z�t�^¡��`EZ½Õ��� �^���� ��v¡¤v�����t¨�EL4 6L4 � ��: EO4I6 � � � ©n ��®¤�  «�» D �v¢Z¢S� P ½ � ¢�¬�����«/��¤¥­£�t���B°)�£� % � � ��� � 6O= � ) � � ( ½ �n�^�1¤¥�EO4I6L4 � ��:<EO4I6 � � � :0EL4I6T= � )� � � :0EL4 � � 4I6 -c½ l�£�1�z­£­£»�¨!©8���z����¬�¢Z� � #REO4 * » D �v¢Z¢S� & ½ V1% � ( ¨#EO4I6"¤¥�z�t�v¡���EO4I6 � ��� ���8EO4I6>4 � �`: EO4I6 � ��� ©n ��®¤� �£�}¤¥­£�t���d°G�£� % � � � � � 6L= � )� � � ( �z�n«/�¥�@�W¡��t½ * ¬�� E����v�B°G���W�}¤¥�z�t�^¡fE � ��� ½8�X�]E�°!�!�v��¤¥�z�t�v¡�E � � ��� >�v�5EO4 � ��:0E � ��� # EO4I6 � � � � % EL4I6 � ��� ( 4 ��½]\!�/¨^EO4I6L4 � ��:<EO4I6 � ��� : % E � � � ( 4I6 -�½�X�%9}°!�!�v�l���t�3¤¥�z�t�^¡ E � ��� ¨B�� >�v��EO4 � � :<E � % E � ��� ( 4 � � � � � :<E � ��="� # % EO4I6 � ��� ( 4 6 � «�¬���� #EO4I6 � � ��� ½:¾n ��£��­º�������v¡����v���£�$¤¥�z�t�v¡��d° «�»9E � �+= � # % EO4I6 � ��� ( 4I6 � «�¬���� # EO4I6 � - EL4 68½�n�^�1¤¥�t¨ EO4 � � # % E � ��� ( 4 � EO4I6 � ��� �M���1°K���`EO4 � � 4I6�- :<EO4I6 � ��� :<EO4I6L4 � �/½>b

�rx®wUyW{£{)�%#����dy^ >q5�S�vu�q sB��w�w�qtsB�vq5� ( �By!~�u � �B �rx ( *��vq �5Ë"��w/�v�)y&�>x��vsB��w�w�qtsB�vq5� ( �By!~�u� ��$u��.�§q+s^{®�.�T*��^qÕ{ yÌ�v�¥x@sBqÕx��Z�^u�q��:�/�!{®qty!w�yW{ ( q"9��dy���w � qB{ºq"� qzw1���$=&Î�{�{��¥qz�V�ayÌ�vq+s^{®�.�§q5�b=>?��Kx��Gy!wqVvUy�sB��sB��~:� �! ª�vu�q�:�/�!{®qty!wPy�{ ( q"9��dy�9UqB{®�B�C¿�G���� �!À¼xºw � � � � � � � =� ��� #��� ����� ��� "�� ����� ( �

p�u�q¼~��vqtsBq5�>x®w ( qVvUyB�G~/{®q5�$s^{®qty!�¥{)� xºw@�>x@szy!�^q��vuUy!���/qB{®qz�¥x®��w@�Ôw�������w/{)� svuUyÌw ( q��^u�q¢�¥�^�N*UsB�N*��vq$�! Á�vu�q( �dyÌ~�u�#F�vu�q"�)yW{��¥�Õx®w@�:*UsBq��G���^~�u/xs�z���t ��v�%� ��w�qÕs^{º�:�T*��vq { yÌ�v�¥x@sBqG�v� y!w��>�vu�qz�5=<?�w> �y�sB�5#b*@�¥q5� �vu�q{@y!�v�¥x@sBq��G���^~�u/xs�z���¼�v�Õu�qB{º~�x�{£{)*@�¥�v�By!�vqG�vu�q�9lqzuUy5A>x®�����B ��vu�qS�v�dy!w@�y ����N�Õy!�¥x®��w�= �:��w@�¥q5�p*�qzw1�¥{)�%#b��qqVv��vqzw@�Õ�vu�qZ9��vqty%�/�^u��B ª�p*��}x®w:A�q5�¥�¥x ( yÌ�¥x®��w@�,��{£x ( u/�¥{)�%=,É3qz��; ��b� ; � 9UqSyK�v�dy!w@�y ����N�Õy!�¥x®��wÕ�B YQ ;

�t�

Page 20: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

ab

c

d

e

χ a

abcde

abcd abce

aceabd

bcde

bcebcd

bdbcacab

a b c d

be

e

dececd

cdebde

ade

acde abde

abeacd

aead

abc

ac

Ø Ø

b’

c’

d’

e’

b’c’d’

b’c’d’e’

b’c’e’ b’d’e’ c’d’e’

b’c’ b’d’ b’e’ c’d’ c’e’ d’e’

b’ c’ d’ e’

�rx ( *��^qG�5ËUDnp�u�q��<xºw ( {ºqK~U�!x®w/�¢�/qB{®qz�¥x®��w�# � Zy!~�~/{£x®q5���v�G�vu�qZs^{®�.�T*��^q��¥~Uy�sBq��! ¡�rx ( *��vq �x®w1�^� Q ; � = ?�w½Æ�qtsB�¥x®��wPQ #]��qÕqVv ~/{®���^q5� �vu�q�9lqzuUy3A�x®���G�! »���$u�qzwSA>xºq"��q5�%y%�K��~lqz�dy!�¥x®w ( ��w �vu�qy!w/�¥x)� y!�v�^�!x���s^{º�:�T*��vq<�¥~Uy�sBq � ;>F��¡��#Uy%�x�{£{)*@�¥�v�By!�vq5��x®wq�rx ( *��^q�QU=�g$�B�Ò��qt c���7� yW{£{)� sB��w@��x��/qz���vu�q9UqzuUy3A>x®�����! ª�v�By!w@�y ����N� y!�§xº�>w@�n��w��vu�qSs^{®�.�T*��vq�{ yÌ�v�¥x@sBq%#&� � ��� ��� y%�:x£{£{�*@�§�v�dy!�vq5� x®wq�rx ( *��^qG���%=

;

� ;>F��¡�

; �

� ; �cF�� �¶�

�� �� � �

� � � � � � � � � 4 � � 4 ��� �

�� � � 4�

�rx ( *��^qG���%DWXYv �vqzw@�>x®w ( ���v� yK{@y!�v�§x sBqZ� ���v~�u/x��T�f qZuUy3A�q<�¥qzqzw"�vuUy!��yW{£{}�vu��vqzq<�/qB{®qz�¥x®��w@�ZyÌ�vqGs^{º�:�¥q5�"y!w@�"sB��w1�§xºw:*��%*@�"=�Î�~�~Uy!�^qzw1�¥{)�%#8yW{£{}�vu��vqzq

�/qB{®qz�¥x®��w@�rx®w@�:*UsBq�wUy!�N*��dyW{>{ yÌ�v�¥x@sBqW�G�>�v~�u/x��T���;� � ��� � � ��b� � � � 4 � � 4 � =Og��B�#�yp�Fy�~��vqB{)*@�/q$�v�t�/q"�G��w���¥�v�By!�¥x®w ( �vu�qÔ{ yÌ�v�¥x@sBq�� ���v~�u/x��T� ~��^��~Uqz�v�§xºq5�$#.��q��§u����%�^uUy!�yW{£{3�vu��vqzq��/qB{®qz�¥x®��w@�$yÌ�vq$�����/qz�:~��vq5�¥qz�NA/�x®w ( =

Q%Ë

Page 21: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

¥�¦ �:n�i3�@o ��©c§0§ Õb/�-:³%¬I2Z{U|%/¶-@°t}%25¬I25°c/¶|%- 6 � ;>F��¡� � ��b� � ; � F�� � �µ¯p4Ê2�|p4Ê}p254�{�4T2"6"254V15/¶-.³BÖt°¶¸.¯%°Z/s6�/ ´_ ��wa °¶¸:25-�_qH � ��Sa,H�� Ã��� �!�#"�$ D �v� ��°!�v���W��� � �/½[, � � � �£¢Z¦>­��£�v���� 1��� ��7 ,54I6 - ,�- � 4 68½ Ù��S¢�¬����¼�� >�z© �� 1���,54 � � � � 4 �F¨��t¡�� 4 �Q7�,54 �O4I6�-]-,54 �3- �f4 �L4 6�-3�t¡������/¤¥� �)���1°R6 ¤¥�t¢K¢�¬���� % ¾n ��v�W¡��v¢ P ½ & � ( ¨�� 4 ��7,54I6L4 �G-2,54 �G- �f4I6]4 �8½ % �n�W���®¤¥�S�� >�G�£¢Z¦/�t¡��¥�z�1¤§�Z�z��¾n ��v�W¡��v¢ P ½ & ��¨3©n ��®¤� )�z­£­£�z©n��¬>����� °!¡¥�B©��� ���z¡��t¬�¢K�v�!�}«1�W¤�Ða�£�!��� % � � 6 ( ½ (R* » D �^¢Z¢a� P ½�� % « ( ¨ , - � 4 6��£¢Z¦>­��£�v�L,54 �0- � 4 6 4 �Á½�\!�/¨1©8�¼���v�d°Õ�W��­£»¦�¡��z�t���� ��:Ö1¡�����¤¥�t�!�<���£��¢Z�v�!�B¨,� 4 �J7J,54I6L4 �+-F,54 �Á¨����n¡��dËW¬��£¡��d°S«!» %U& ( ½�X�2� �£�ª¤¥­£�W���d°�¨#, � � � �£¢Z¦>­��£�v� , �£�ª¤§­��W���d°À½FØ}�/°�¨!�Ñ�Y, �£�}¤¥­£�W���d°�¨#,54I6O4 �5:<,54 �8¨!©n ��v�1¤§�$�� ��:Ö1¡����

¤¥�W���¥�z�£��¢K�v�!�Á�£�8��¡��£�!�®�z­�½Ù��G������¬>¢Z�G���^���� ��v¡5, ���W¡ � �£�G¤¥­£�t���B°�½�, � � � ��¢K¦�­£�£�v��«!»"¾n ��v�W¡��v¢ & ½��Õ�� /�z�S�� ��^¡��Õ�¥Â��������

���<#� � 4I6 � �f4 �U��¬1¤� G�� 1�z�5��� � � �%�z�/°����[:<, � % � 4I6 � ,54I6 ( ½�8�t�>���dËW¬��v�!��­�»!¨��<-����Ϩ!¦/�t�����£«�­£»!¨��� :��$½��aµzÆ��]½K©8�Z�z����¬�¢Z���� 1�z��� 4I65¤¥�z�W�v¡���,54 6 �z�/°5, � � ����¨U�����/¤¥���t�� ��v¡�©n�£���Z©8�Z¤v�z��¢S�zÐt�¼������v¦!©n�£������¡��t¬>¢Z�v�!�d¨W¬������>���� �����¡¥�z�����£���£�!����»����.� � ½Ù��} /�B�t���� �¡��v��¤v�����v�� % � ( �� # �f4I68¨ % « ( � # � 4I6�«�¬>� � #�,54I68¨1�z�/° % ¤ ( � #5,54I6Á½� ��� �X� �� #Q,54I6 �� ��v� � # � 4 6 ����� 4 � 78,54I6L4 �5: ��78,54I6+-3, :<,54 �Á½� ��� D �v� � #Q,54I6 � � #�,54I68½Y\!�£�1¤§�f,54I6 � �%�f4I68¨ ,54 6+: � 4I6 � ��� �z�/°X, : � � � � � ½2�n�z©$¨ ��- � ���¢K¦�­£�£�v�F«!» D �v¢K¢a� P ½�� % ¤ ( �� 1�z��� 4 �R- � � 4 �5:0,54 �F½]\!�/¨�� 4 �`78,54I6O4 �+-3,54 68½

� �� � #5,54I68½ �Ã���� ��v¡L,54I6 � ��� ¤¥�z�t�v¡��O, �W¡], ¤¥�z�W�v¡��L,54I6 � ��� ½l�����v�£�� ��^¡ª¤v�����t¨^,54I6L4 �5:0,54I6 � � � ½�X� �) #�,54 F¨�� � ��� ¤¥�z�W�v¡�� �$¨!�����f4 �J78,54I6R: � � � � 78,54I6 � ��� - , � � � :0,54 �F½D �v� � # � 4 )���1°�­£�v��,54I6:��f4I6 � � � � � : � ½ ���`4 ��: ��� � % ��� � � � ( 4 ��� � ��� ½ �É�z©$¨, - ��� � % ��� � � � ( 4 ���/¨n��� � # % ��� � � � ( 4 � �S�£¢Z¦�­£»!�£��� � # % ��� � ��� ( 4 � �1½�¾n !¬��d¨�f4 �`7J,54I6L4 �+-����`4 �J78, � ��� -F,54 �Á½>b

ÎÒ�/qB{ºqz�§xº�>w � � yÌ~@�ySs^{®�.�T*��^q�¥~Uy�sBq � ;>FV���n��w/�v�ay��T*U9@�§qz�$�B Fx®���¥qB{I � ;��cF���� �� � ��#/u�qzwUsBq�x®�� y!~@�¼�^u�qZ{@y!�^�¥x@sBq�� � � � � � ��w/�v���vu�qK{@y!�v�¥x@sBq � ��� 4 � � 4 � =Zf q×yÌ�vqKxºw/�vqz�vq5�§�vq5� xºw �vu�qSwUy!�N*��vqS�B ��vu�q5�¥q{@y!�v�¥x@sBq'�G���v~�u/x��T���$=W�rx®���¥�,��q�q5�¥�dy!9/{�x��¥u��vuUy!�

���0oSoqj ��©c§ � *V-�� ����� � �, ¯�-_���a � _���a � _>H�� ��a,H��¡Ö 0 /�°¶¸�2V±5+:¯%¬I/¶°c²</ ´,_SÖ�|%4ZatÖW/s6«5¬I|B6"2�}.Ã,�. - � _���at��H�� �P_>H�����a,H�� �P_qH�� ��aÂH���Ã

��� �!�#"�$� ��� , � � � � , �£¢Z¦�­£�£�v� % , � � ( 4I6�78, � � , � � � � ,54I6

, � � � � � �£¢Z¦>­��£�v� % , � � ( 4I6J7�� � � , � � � � �f4I6¾n ��G­®�z���Z��©8� ¤¥�t�!�<���£��¢Z�v�!���Z���W�t�v�� ��v¡S�£¢Z¦�­£»+, � � -.,54I6 7 � 4I6Á¨É©n ��£­��S�� ��GÖ/¡����S��©8���£¢Z¦�­£»% , � � ( 4I6J78,_7 � -F, � ��½3�t¡n���£�1¤§��, � ��- % , � � ( 4I6n¨^,_7 �<-3, � ��½�X� , �£�ª¤§­��W���d°À¨1, � � � � , �£¢Z¦�­£�£�v�H, � � �£�ª¤§­��W���d°S���1°`, � ��-3,�½�8�t�����dËW¬��v�!��­£»!¨ % , � � ( 4I6`7, : % , � � ( 7��0:3, � �$½

Q��

Page 22: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

� ��� ¾n 1���O,54I6 � � 4I6R: ,54 687�� 4I6 �@�t­£­£�z©n�3�@¡��t¢ �� ��$°!�§Ö1���£���£�t�S���M¤¥­£�t��¬>¡��t½r�X�M�v�£�� >�v¡>, �W¡�� ���n¤¥­£�t���d°�¨�� ��$¡��v��¬>­��:�@�W­£­��z©n�n°!�£¡��B¤¥��­£»S�@¡��t¢ % � ( ½nØ:����¬>¢Z�$���^���� ��v¡�, ���t¡ �%�£�¤§­��W���d°À¨U�z�1°K�� 1�z� ,54 6 : �f4I6% �v­£������ ���¤¥�W�1¤¥­£¬����£�W�a�£�n��¡��£�!�º��­ ( ½\!�£�1¤¥�L, � ��-F,54I6>7 �f4I6F¨ % , � � ( 4I6�-�,54I6>7�� 4 68¨z�W¡ % , � � ( 4I6 ����,54 6>7 �f4I68½ * ¬��B¨ ,54I6 � ��,�z�1°�� 4I6 � �%����¢K¦�­£»}�� 1�z�H,54I6 � �f4I6�� � , � ��¨t�z�1°�«!»$¾n ��v�W¡��v¢ & ½���¨ ,54I6 � � 4 6 ��� % , � � ( 4 68½\!� ,54I6 � � 4I65: % , � � ( 4 6ɽ>b|ÔqtszyW{£{Ï�vuUyÌ� y�{@y!�v�¥x@sBq �G���v~�u/x��T� � ��@� � � x�� szy�{�{®q5��y ¦ nLoqnLoqnbi�Ó ¦ r�l!o xI �xº�Õ~��vq5�¥qz�7A�q5�

9U�>�vu �vu�q'�Gqzqz� � ���y!w@� ¥�!x®w ��� �}�>~Uqz�dy!�^����� -/x®�¼x��¼szyW{£{ºq5� y�oq�:�:g ¦ nLoqnLoqnbiBÓ ¦ r�l!o lÏxI nxº� T*@�¥�~��vq5�¥qz�7A�q5�8�vu�q,�Gqzqz�n�>~Uqz�dy!�^���5#!�vuUy!�8x�� ��� ���:�VH���� � H�� �"�UH���#3 ����}yW{£{ � F ��O �Z= � *�� ( �1yW{Uw��B� x��n�v��¥u��B���vuUyÌ���/qB{®qz�¥x®��w@��x®w@�:*UsBq×yµ�G���v~�u/x��T����w��vu�qSs^{º�:�T*��vq�{@y!�^�¥x@sBq5�$�vuUyÌ��x��,�Sx��:�$y3��9lqz�T�qzqzw��vu�q�T���@=�?��}x��$y��Gqzqz��u��%�G�%� ���v~�u/x��T� �vuUy!�:~��vq5�¥qz�NA�q5�:�vu�q ¥�!x®w���~Uqz�dyÌ�v���W*�w@�/qz�,�¥~lqts^xIdMsZsB��w@�>x®�¥x®��w@�"=f)qtdU���§�$q5�¥�dyB9/{£x��¥u�qS�vuUy!��q"A�qz�7���/qB{®qz�¥x®��w�x���yµ�Gqzqz�$u��%�G�p�G���v~�u/x��T��=

¥�¦ �:n�i3�@o ��©c§ �8*)´ � ;>FV��� � ��b� � ; � FV� � �Z/)6Z¯�6"/�-:³%¬I2\{U|%/�-0°W}%23¬I25°c/¶|%-UÖ�°¶¸.25-� _ ��a��VH�� �P_>H�� ��a,H��

��� �!�#"�$ D �^� �)°!�^���t��� � �/½ D �v��,�¨U�W¡ ��¨�«/�Z¤¥­£�t���B°�½¼¾n ��v� , � ���£�Ô¤§­��W���d°����1°9, � �a: , � � 4 63:,S7 � 4 6 «!» D �^¢Z¢a� P ½ & A^% � ( ½�8�t�>���dËW¬��v�!��­�»!¨!«!» D �v¢Z¢S� P ½�� % � ( ���1°�¾n >�v�t¡��v¢ P ½ & �

% , � � ( 4 � : % ,_7��f4I6 ( 4 �5:<,54 �J7�� 4I6]4 �: ,54 �J7 � 4 �]4I6 - :0,54 � � � 4 �L4I6 -: ,54 � � �f4 �

\!��©8�$�z����¬�¢Z�:���v�£�� >�v¡f, ���t¡�� ���n¤¥­£�t���d°�½�X� , � � ���n¤¥­£�t���d°�¨!�� ��v�J, � �<:0,54I6 � � 4I68¨����1°��$��­£���W !�M�§ÂÌ���v�������W�S�z�U�� >��z¡��t¬�¢K�v�!�F�z«/�z�t�n©n�£­£­1��¬��a¤¥�t½Ù���������¬>¢Z��, � ���£�}���W�¤¥­£�W���d°Õ�z�1°×�� 1���Z,54I6 : � 4 68¨/���£�1¤§���W�� ��v¡�©n�£���X, � � �z¡����£�S�� >���¥�z¢Z�����!���v¡��t��­ ,54I6 � ,54 ��¨t©n ��®¤� S�£�}� * �!�t­£�d���a��­��W�v«�¡¥���z�1°��� ���¤§�t�1¤¥­£¬����£�t�S�£�Á�v�!�®°!�v�!�B½\!�£�1¤¥��, � �%�£�:���t��¤¥­£�t���B°S�£�}�£�}�£�G�z�G�£�!���^¡��t�z­ % , � � ( 4I6 � % , � � ( 4 ���½ * » D �v¢K¢a� P ½ &)A^% « ( ¨ % , � � ( 4I6�:,54I6 � � 4I6Á¨!�z�/°�«!»�¾n >�v�t¡��v¢ & ½��>¨t�� ��v¡��:�¥Â��£�����n¬>���®Ët¬>�n�v­£�v¢Z�v�!���OE �<# ,54I6 � ,54 � � E��;# �f4I6 � � 4 ����¬/¤� �� /�z�f, � � � � E � � � , �z�1°8, � � � � E�� � � �$½f\Ì�1¨1, � ��:E � � E��"�z�n�� ��z©n�G�£�S�� ���Ö1�W¬�¡��t½É�����¬��a¤¥�v�n������ ��z©"�� /�z� % , � � ( 4 �M: % E � � E�� ( 4 �5:<E �`4 � � E��L4 �F¨!�z�1°¼�£�F�£�F�d�����£�v���n�����@�W­£­��z©��� ��}����¡�¬1¤¥��¬>¡���z�3�� ���¦�¡��!�z�3�Ñ�M©8�Ô������¬�¢Z���� /�z�L,54 6��z�1°�� 4I6Õ«1�W�� G¤¥�z�t�^¡ % , � � ( 4I6��@È�Z= � + = :�= � � = : & ½2�n�¼�t�v�>�v¡<��­��£��»�£�n­£�t���8�� >�v¡��v«!»!½Ù��nÖ/¡����:��¬�¦>¦1�W���$�� 1�z� �� # % , � � ( 4I68¨���� % , � � ( 4 �R:3, � ��½3�X� �) #�,54I6��� ��v��,54 �R:0, �z�1°K�Ñ� �� # �f4I6�� >�v� � 4 �R: ��½ 8­£�d�z¡�­£»�¨>�Î� � �£����G�v­£�v¢K�v�!�n�z�Á���^���� ��v¡B¨1�� ��v�Õ�� ��¼¤¥�t�1¤§­�¬>���£�t�S�X�t­£­£�z©n�Á��¡��£�!�º��­£­�»!½O\̬�¦�¦/�t���� #5,54I6Á¨W�£¢Z¦�­£»!�£��� � + : � � �z�1° E � 4 �5:<, � �$½�� + :�� �}�^­����f,54I6+: � 4I6Á½H\!� �� #5E � ¨^E � 4 �5:0E � ¨����1°% E �� E � ( 4 �5: % , � � ( 4 �5:0, � �<:0, � � � E � :<E � 4 � � E � 4 �Á½

Q%Q

Page 23: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

(X ^ Z).

X.

Z.

Y

Y

ϕ

ϕ

ϕ

X

Z

δ

δ δ

δ

δ

δ

δ

1

3

3

2

3

1 2

X ^ Z

X

Z

�n�§ÂÌ�B¨t©8�������¬�¢Z� � # % , � � ( 4I6Á½3¾n >�v¡����z¡��n��©8�$¤v�z���v�d½�3�£�� ��^¡ � # % , � � ( 4 F¨W�t¡F���W�d½� l��¡����B¨!©Á�n��¬�¦�¦/�t����� # % , � � ( 4I68¨U���S���v�£�� ��^¡ � + �>�t¡ � � : � � ½ % , � � ( 4 �3: % , � � ( � ��� # % , � � ( 4I6 � % , � � ( 4 ���½ * »

δ 2

XY

YZ

δ 1

δ 1

δ 2

δ 2

(X ^ Z).

X.

Z.

ϕ

ϕ

ϕ

δ 1

Y -{p}X

Y -{p}ZX

Z

X^Z

Z. = Z-{p}

X. = X-{p}

(X^Y). = X^Z -{p}

σ

σ

σ

¾n ��v�W¡��v¢ & ½ �>¨ % , � � ( � ��� � � + � # ,54 6 � ,54 �}�z�1°�¤§�z�t�v¡�� % , � � ( � ��� : E �Ͻ % , � � ( � � � � � � � # �f4I6 � � 4 �Á���1° ¤§�z�t�v¡�� % , � � ( � ��� : E � ½ 8�W�����dËW¬��^����­£»�¨!E � 4 � � E � 4 �3: %e% , � � ( � � + � � ��� ( � % % , � � ( �� � � � � � � ( : % , � � ( � ��� : % , � � ( 4 �Á½¾n ��£��­£�d�B�t�v� � ¬>������ ���¤v������©n ��v¡�� � # % , � � ( 4 8½ D �v� � # % , � � ( 4 8½$¾n ��v� % , � � ( 4 6 ¤¥�z�t�v¡�� % , � � � ��� ( 4 6r½��X�O, � � ¤¥�z�t�^¡���E � � � ��� # % , � � � � � ( 4I6 � % , � � � � � ( 4 ��¨/�� ��v�Õ©8�Ϥv���G¬�����¾n ��^�t¡��^¢& ½�������«1�¥�X�t¡��Õ���ÕÖ/�1°"�� >�G¬����®ËW¬��G¢K���>��¢Z��­]E � �z�/°�E � ��¬1¤� )�� 1�z�8, � � � ��� � ��E � ��� , ���1°, � � � ��� � � E�� � � � ©n�£��  % , � � ( 4 �5:0, � � � � � :3E � � E��9:0,54 � � �f4 �F½* ¬��d¨��Ñ� � # % , � � ( 4 F¨!, � �����v�d°Õ���W�¤¥�z�W�v¡�, � � � ��� ½ �n�z©8�v�W�v¡d¨ � # % , � � ( 4 �£¢Z¦�­£�£�v� % , � � ( 4I6¤¥�z�W�v¡�� % , � � � ��� ( 4I68¨U���1°G«!» D �^¢Z¢a� P ½ A ¨ , � � � % , � � � � � ( 4 ���S¢�¬�����¤¥�z�t�v¡�, � � � % , � � � ��� ( 4 ��� � ��� : % , � � ( 4 �Á½ D �^�>E�:0, � � � % , � � � � � ( 4 ���A#� % , � � ( 4I6 � % , � � ( 4 ��¨!��� E � � � :, � � � % , � � � � � ( 4 ��� � ��� : % , � � ( 4 �)���}�£�G�� >�¼Ö1�t¬�¡��t½�Ù��$ 1�B�W��¢K�t¡��Ô¤^�z���^�d¹l�v�£�� ��v¡ � #�,54 F¨� # �f4 8¨U�W¡$���t�B½S������ ���Ö1�t¬>¡���©8�Z�� >�z© � #F,54 5���1° � # �f4 Á¨l«�¬��¼�z�!» ���ª�� ����X�t¬�¡�¤§�t¢�«��£�1�����£�t����z¡���¦/�t�����£«�­£�t½�Ù����z����¬�¢K�$�� ��£�$¤¥�W�!Ö1�t¬>¡<�z���£�t�U½:Ø}��«/�¥�@�t¡��t¨l�� ��v¡����¥Â��£����¬����®ËW¬��$¢K���>��¢S�B­ E � # ,54 6"���1°

Q��

Page 24: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

YZ

δ 2

δ 2δ 1

XY

δ 1

δ 2

δ 2 Z. -{p}ϕ

(X ^ Z).

Z.

ϕ

ϕ

Z

Y

(X ^ Z) -{p}

{p}

{p}

ϕ

{p}

X^Z

XY -{p}

Z

{p}

Y -{p} = Z.

(X^Z). = Y-{p}

X

X. = X-{p}σ

σ

σ

X.ϕ

E��@#��f4I6Õ��¬1¤� G�� 1���>, � � � � E � � � , �z�1° E � � E���� � ��½% , � � ( 4 �R:3E � � � : E � E�� � ���

: E � � � � � E�� � ���: , � � � � E � � � � :3,54 � � �f4 �

¾n ����t�� ��v¡:�� �¡��v��¤v�����v���z¡��� 1�z�1°Ì­��B°����£¢K��­®��¡�­£»�½Hbp�u�qz���^q"� �U=®����sB�%*/{�� uUy5A>qZ9Uq��§�dy!�vq5��y%��yGsB���v�!{£{@y!�N�Õ�v�G�^u/xs�{ºq"�×� y -����¼yW{®�vqz�vwUy!�¥x)A�qB{)�%#0��qZsB�%*/{��uUy3A�qt*@�¥q5�G�^uUy!���vu�qz���vq"� �v�'dU���¥���/q"� ��w@�¥�v�dyÌ�vq��^uUy!� � _���a��VH�� � � 4 _>H�� �<a,H�� =�f)q¼�vu��%* ( u1��vuUy!�K�T����>x �Fqz�vqzw/�Z~��v�/�B K�"#F�>w�q��$u/x@s^u �Õy%�/q yB9U*�w@��y!w/��*@�¥qG�B �p�u�qz�>�vq"� �U= �5Ë�y!w@� ��w�q<�$u/x@s^u� y%�/q�w��×�Gqzw1�§xº�>w �B 8x®�,�$uUy!�vq"A>qz�5#:�qz�^qZA�yW{)*UyB9/{®q%=

Æ��p�GqG�B ��^u�q��T*U9��¥{®qz�¥x®q5�µ c�%*�w@��x®w5�^u�qG{@y%�¥�' �q"�hszy%�§q5�Z�! �pÔu�qz���vq"� �U=®�t��yÌ�vqGx£{£{)*@�¥�v�dyÌ�vq5�S9.��rx ( *��vqG�5Q = � 9@�¥qz�NA�q��^uUy!�Z¿ �y��ÀZ� ¿�G��K�LÀ ��¿ ���K�LÀ��§� �<O>¿ �K�LÀ.H��)y!w@� ¿ �K�LÀ.H�� � ¿��LÀ.H � � ¿ � ÀZ�¿ � ���+�sÀ.= g$�B� ¿ �K�LÀ �/�/q5�Õw����+sB�BA�qz� ¿ �y��À:H�� x®w � ����� � � y%�×xs���§�5�B ��vqzw �vu�q"szy%�¥q%= È����vqz�BA�qz�3#�$u/x£{®q&¿ �y�LÀ�x��GsB�BA�qz�vq5�S9:� 9l���vu½¿�G��y��À y!w@��¿ ���K�LÀÕxºw � � � � � � #Éw�qBxº�^u�qz��¿�G��y�LÀ.H�� � ¿�G � � � À�w����¿ ���y��À:H�� � ¿ � � � � ÀZsB�BA�qz�t¿ �K�LÀ.H � � ¿ � � � � À:=\Æ!x®w ( {®qZ~U�Ìxºw/�,�/qB{®qz�¥x®��w@�$w�qzq5�Õw��>�~��^q5�¥qz�NA�q�sB�BA�qz�¥x®w (�vqB{@y!�¥x®��w@�§u/xº~@�$= ���B�q"A>qz�5#

���0oSoqj ��©c§ *s´ � ;>F��¡� ����0� � ; � F�� � �Z/s6¯<6"/�-:³%¬I2\{U|%/¶-@°W}p25¬I25°c/¶|%-UÖW¯p-@}, ¯�-_ � ah/)6«3¬­|!682V}BÖ,�. -Z_ � a «V|%1325476,_ ¯%-@}×a

°¶¸.23-� _ � at��H�� �P_qH � � a,H��

��� �!�#"�$ D �^� � °!�^���t��� � � ½ * �d¤v��¬���� �������W¡<°!�v¡�¦�¡��v���v¡��!�£���/¨ ,54����2� 4��<����� % ,��*� ( 4��3½¼Ø}�/°Õ«1�d¤^�z¬����t¨�� >���¬�«�­®�z�����®¤¥�$���䥭£�W���d°S��¬�«����v���:���n­£�z©8�v¡8���v¢K��¢K��°!¬�­®�z¡B¨ ,h���1°�� �d�t¤�  ¤¥�z�W�v¡>, � �$½�X� �� #Q,��2��¨��� >�v� �� #Q, �W¡��$¨!������ ���¤¥�W�1¤¥­£¬������W�K�@�t­£­£�z©n�F��¡��£���®��­�­£»!½

Q �

Page 25: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

b de f

c

bcdef

cdef

def

bdefbcde

cefbde cdebcd

bc bd cd ce de ef

e fdcb

Ø

bcf

bf

bce

be cf df

cdfbef bdf

bcef bcdf

Ø

b’

c’e’ f’

b’c’f’

c’f’

b’c’e’

b’c’ b’e’ c’e’

b’ c’ e’ f’

b’c’e’f’

c’e’f’

e’f’

b’e’f’

b’f’

�rx ( *��vqG�3QUD�ÎÏ��x®w ( {®qZ~U�Ìxºw/�Z�/qB{ºqz�§xº�>w�# � D �^� � #,��2�$½ D �^� , : ,��2� � � � � � � : ,�� � � � � � ½ \!¬�¦�¦/�t��� � � : �<% �W¡ � � : � ( ¨r�� ��v�,54���: , : % ,�� � ( 4��3½ * »G­£�z©8�v¡����v¢K�£¢Z��°!¬�­®�z¡��£��»t¨1, � �G: � � � � ½X\!�1¨ ,54 � :G, � �G: % , � � ( 4���£¢Z¦�­£»!�£��� % ,��2� ( 4�� ��� � ,54����2�f4��3½�X�F���v�£�� >�v¡�� �%�>�t¡�� �5: � ¨!©Á��¢�¬����ª¤§�t�����º°Ì�v¡¤v�����v�B½�X� � # % ,�� � ( 4 ��� ��v� �� ��v¡����¥Â��£������E ��¬1¤� %�� 1���JE : ,��*� � ��� ½ * »"¢K�v�v�a°Ì������¡���«>¬����£�!�£��» % ���v��F°!�^­�¢S�z� V �F�t¡��M�c�z­£��� & P � ( ©8�$ 1�B�t���� ��¼��¬�«>����¡�¬1¤¥��¬�¡��K�� ��z©n�G�£�S�� >�$Ö1�W¬�¡��¼©n ��v¡����� ���¤¥�z�t�v¡��£���Z�d°Ì�t�v�

q Xq Z

X

X Z

Z

X^Y Y^ZX^Z

Y

X^Y^Z

V

q X pq Z

q q Zpp

p

X

�z¡��G­®�z«/�v­£�d°"©n�£��  �� �� ��¦�¦�¡��t¦�¡��º�����G�^­��^¢Z�v�!���B½ % ,�� � ( 4 � : E - : EO4�� � ,54���:., - � E - : % , � E ( 4��3¨� 4 �8:0E - � � - : % E � � ( 4��Õ�z�1° % , � � ( 4���:<, - � E - � � - : % , � E � � ( 4��3½3¾n ��¼¤¥�t�1¤§­�¬>���£�t�K�@�W­�­£�z©n�B½

Q%Ø

Page 26: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

l�£�1�z­£­£»G©8�Z��¬>¦�¦1�W��� � # % ,�� � ( 4 F¨r�£¢Z¦�­£»!�£���`,�� � � ��� # % ,��*� ( 4I6 � % ,��2� ( 4 ��}�z�1° % ,��2� ( 4��[:% ,��2� � � � ( 4��3½�X� �3 #R,54 % �t¡ � # �f4 ( �� ��v¡������:����¦�¡��t«�­£�v¢ �����/¤¥� ,54��5: % , � � � 4��3¨>©n ��v¡��X, � ��� # ,54 6 � ,54 ��z�/°Z«!»�¾n ��^�t¡��^¢ & ½���, � � � � ��,�� � � ��� ½�X� � #�,54 % �t¡ � # �f4 ( ©8�S 1�B�t�S�� �� ¤¥�W�!Ö1�t¬>¡<�z���£�t� �� ��z©n�)«/�v­£�z©$½ �n�v¡��R,54��: % , � ��� ( 4��:

X ZV

X -{p}

X Z

X^Z

X ZV -{p}

q X

p

q Z

q Xq Zp

,�� � � � � � � � : % ,�� � ( 4�� � � -� � ½ * »K¾n ��v�t¡��v¢ & ½ A % � ( ¨t�� ��£�n�£�}��¤¥�z�W�v¡}�£� % � - � 6 - ( «/�d¤v��¬����% ,54�� �� � � � ( 4I6 - : ,54��!4I6 - �� � � �

: ,54I6L4�� �� � � � 4 b

pÔuUy!���^u/xs���vq5�T*/{®�aszyÌw�w����Z9Uq ( qzw�qz�dyW{£x)Çzq5� �v�+y�{�{��B ������� � � x��ZyW{��¥���/q"�G�>w@�¥�v�dy!�^q5��9:�&�rx ( *��vq�5Q'�$u�qz�vq'¿ ���y��ÀZ�$u/x@s^uÕx���w����$s^{®�.�¥q5��sB�BA�qz���»¿ �y��ÀZy!w@� ¿ ��� �3��À�-%9U*��t¿ ���K�LÀ.H � � ¿ � �I�+��À�/�/q5�:w����sB�BA�qz�Z¿ �y�LÀ.H�� � ¿ � � � � À.=

Î {@y!�^�¥x@sBq,�G���v~�u/x��T�8� ��b� � � x��W�vy�xs�K�v�t9Uq¼y��sn����®itl"�0o r ¦ n�o>n�o>n�iBÓ ¦ r¶lBow#t����É�Æ �'#WxI � ����yW{£{ � F ��O �Z# �F� ���:��H���� � H�� ���UH��"y!w@� � � � � � F(� � � � �K�v� ( qz�^u�qz�}x)�G~/{)� ��� � �:��H�� � � H�� � �UH���=�n�^��~Uqz�v�§xºq5���B F{®�B��qz���¥q"�Sx®u��%� �%�G���v~�u/x��T����szy!w�9lqZ ��%*�w@�Õx®wS~®�5Q3�K=��$nbi5nb���sj@i�� �L©c§!� *)´ � ;>F��¡� � ��0� � ; � F�� � �Z/)6¯�6"/¶-.³%¬I2�{U|%/�-0°W}%23¬I25°c/¶|%->°¶¸.25-

� � ��� ��� ����b� � � � 4 � � 4 �/s6¯�¬I| 0 234Z6"25Á�/)¸:|%Á�|%Á�|%4c{0¸./)6"Á 0 ¸.25->4T2"6"°c4�/¶«5°c2V}�°c|�°¶¸.2'68+ . ¬I¯%°c°c/¶«�2�|T´«3¬I|B682V}×68+ . 6"25°¶65Ã��� �!�#"�$ ¾n >���n�£�}���Z�£¢Z¢K�d°!�®�z���ª¤¥�W�����BËt¬>�v�1¤¥�����M¾n ��v�W¡��v¢ P ½ & P ���1° D �v¢K¢a� P ½ &�V ½]b

Î�{®�vu��%* ( u½�/qB{®qz�¥x®��w@�"#�� #$y!�vqÕ{®�B�qz���¥q"�Sx®u��%�G�%� ���v~�u/x@s���w/{)�%��w%�vu�qq�z*U9/{ yÌ�v�¥x@sBq"�B �s^{®�.�§q5��T*U9@�¥qz�V�"#rxº�Kx����T*:�+s^x®qzw/�5#�9UqtszyB*@�¥q yÌw1�¥x)� yÌ�v�v�!x��)s^{®�.�T*��^q��¥~Uy>sBq5�Zy!�vq�sB�%�G~/{®qz�vqB{)� �/qz�^qz�N�Sx®w�q5�S9.�T*@�¥�S�vu/x����z*U9/{ yÌ�v�¥x@sBq%= � p�u�q ( qzw�qz�dy!�^�����"#�`\H���#n�B �y!w:�5s^{®�.�¥q5�w�T*U9@�¥qz��` szy!wS9Uq��/qz�^qz�N�Sx®w�q5�S9.�qVvUyB�Sx®w/x®w ( �vu�qZs^{®�.�¥q5���§qz���$sB�BA�qz�vq5��9:��`�=I�'f)q��vu�qz�vqV ����vq�vy3�Õ�vuUy!���/qB{®qz�¥x®��w@����xºw@�:*UsBqGyK{®�B��qz��¥q"�Sx®u��%� �%�G���v~�u/x@s��v�dy!w@�y ����N�Õy!�¥x®��wÕ�B ª�>w�qZs^{º�:�T*��vq��§~Uy�sBq���w/�v� y!w����^u�qz�5=

��� Ü�àvÞvâWåXçÎädèKå�átÜ�ß�ÜvÞvæWÜ<ßnå�á!Þvå�ì ë õzíMÞvÝ�Ý�â3ßÜ¥Ýnå�á!ÞvånÞTÜàÜ0Ü�Þvå�åXçÎà¥Ü¥ÝTäUæFázçÎà�áaÞ^ß�Ü}àvÞzÜàÜÎÜ<æGñrï)Ü�Þ^å�åXçÎà¥Ü¥ÝTäÀÞ^ß�ÜÞ^å�äVß}çÎàVä�å�á�Þ^åçÎÝTä�ÞzÜàÜ1ÝXçÎètî7ÜÎÜ¥å�ädè�ÜyÜÎÜTß�Ü¥èzå�ÝÃÞ^ß�Ü8àKÜÎäBÝ�Ü¥æ�÷ Û ázçÎÝlçÎÝFÞnà�á�Þ^ß�Þvà¥å�Ü¥ßXçÎÝ�åXçÎànä7ÞÀÞzÜàÜ�à<äBè"éBÜÊã�îdÜ¥äVßÜ¥å�ßXçÎÜ¥ÝTä!étâtå3èWÜ<Ü¥æ$èWädålé!ÜÁå�ß�âWÜFçÎèîBÜ<èWÜ¥ß�ÞTÜ®÷FðWädß3ÜTãtÞNß�ã$ÜÎÜ�ä�å�áWÜFçÎæWÜvÞTÜ�ã�Þ^å�á�àyÜÎäBÝ�âtß�Ü¥Ý�ð���ÞvèWæ¢ð�ZêBçÎÜyÜÎæZÞ^å�ä�ß:çÎànàyÜÎäBÝ�âtß�Ü}Ý�ã!Þvà¥Ü¥ÝFäBè"ÜÎê�çàÞUå�áWÜ¥ê�Þvß�Ü8å�äBå�ÞTÜàÜÎêæzçÎÝ�à¥äBètèWÜ<à¥å�Ü¥æ�÷

Q%¤

Page 27: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

� ��� � \�����\�����Z���

� w�qaszyÌw�� y^ >qZyGw:*U��9Uqz�¼�B ª�p9@�¥qz�NA�yÌ�¥x®��w@�,9Uyp�¥q5����w��^u�qZ~��vqtsBq5�>x®w ( �¥qtsB�¥x®��w@�$=\?c N#My%�xs���vu�qSszy%�¥q��x®�vu ( �dyÌ~�uPu��p�G�%�G���^~�u/xs�z���"#3��w�q<�/qVdUw�q5�ZyÕ�^�dy!w@�y ����N� yÌ�¥x®��w��B Â�>x��vsB�^qz�vq<�¥~Uy�sBq5�¼x®w"�vqz�N���¼�B y~U�Ìxºw/�Z� y!~�� ��w��vu�q��¥qz�Z; �! }qB{ºq"� qzw1���$#U�vu�qzw"��w�qSszy!w�& �$uUy3A�qSy��/qB{®qz�¥x®��w � x®w>�$u/x@svu)yS~l�!x®w1�J&O&; ��x)�G~/{)� $�>xs�^y!~�~Uqty!�V���U=t?��Z���%*/{���w����t9Uq���qB{�{®�K�/qVdUw�q5� �BA�qz�Ïy�{�{n�B �; =���*��5#b9Uqtszy!*@�¥q � xs��/qVdUw�q5�"��w��vu�qZ~l�B�qz�Z�¥qz��Q ; #l��w�qGszy!w�uUy5A>q<¿�JbÀ:H�� �ÏÙ=Xg$�B�#@�/qB{®qz�¥x®��w@�Ky!w@���^u�qBxº�¼x®w@�:*UsBq5�{@y!�v�¥x@sBq'�G���v~�u/x��T���»�¥qzq"� wUyÌ�N*��dyW{K=

f q$uUy3A�q�sB��w@��x��/qz�vq5�Õ�>w/{�����x®w ( {®q�~l�!x®w1�,�/qB{®qz�¥x®��w@�,��x)�G~/{)��9UqtszyB*@�§q��vu�q"�Gy!�^q��¥���*Us^u+s^{®qty!�^qz�5#y!w@�×9UqtszyB*@�§q��vu�q"� y!�vqt9Uy%��x@s��v�S�vu�qZ�/qB{ºqz�§xº�>w sB��wUsBqz~��5=W��*��5#U��x®w ( {®q�~U�Ìxºw/���/qB{®qz�¥x®��w@�$szyÌw�9lqZsB�%�G�~U�:�¥q5�b=,�rx ( *��vq �W�Kx£{�{)*@�¥�^�dy!�vq5���vu�qasB�p�G~U�.�<xº�§xº�>w �B �� �Â��x®�vu � =�g����vqZ�^u�q�T*U9/{@y!�v�¥x@sBq�~IÙF��BF��@F����B�

ab

c

d

e

a’b’e’

b’

Ø

a’e’ b’e’a’b’

a’ e’

χ

abcde

abcd abce

aceabd

bcde

bcebcd

bdbcacab

a b c d

be

e

dececd

cdebde

ade

acde abde

abeacd

aead

abc

ac

Ø

a’e’

b’cd

�rx ( *��vqÕ�t�UDnp�u�qZsB�%� ~U�.��x®�¥x®��w��B �� � y!w@�� y!~�~/{£x®q5� �^�G�vu�qZs^{®�.�T*��vq��¥~Uy�sBqK�B Y�rx ( *��vq ��B � ;>F��¡��$u/x@svuw�Õy!~@�S��w/�v�SÙ �B � ; � FV� � ��= �À�!{£{º�B��x®w ( ~®�5Q3�K#���q szyW{£{��^u/xs�×�vu�q��0�®ipkb�®���! ��vu�q�/qB{®qz�¥x®��w �W=�?c ,_ y!w@� a yÌ�vqSx®w5�^u�q5 �qz�vw�qB{��B �y��/qB{ºqz�§xº�>w�#n�vu�qzwS9UqtszyB*@�¥q �%x��Sy��§q"�Sx)�G�®�:*/{@y!�u��%�G�p�G���v~�u/x��T��#B_���a ��*@�¥��9Uq:x®wG�vu�q �qz�vw�qB{K#1y!w@�'_ � a)x��rx®wa�^u�qZ >qz�vw�qB{1xI Fy!w@�K��w/{)��xI Ux®�}sB�BA�qz���9U�>�vu�_ y!w@� aZ=]f qZsvu��.�§q��v�Kx£{£{)*@�¥�v�dy!�^q � � 9UqtszyB*@�§q�x®�:xs��s^{ºqtyÌwPy!w@�×��qB{�{®�c9lqzuUy5A>q5�b=p�u�q��^qty%�/qz�x��$qzwUsB�p*��dy ( q5�Õ�v�×A�x��T*UyW{£x)Çzq � ! #��^u�qZsB�%�G~U�:��x®�¥x®��w �B �� ���x®�vu � ! =�?���x�� ¿yÌ�,�G���vq¼x®w/�vqz�vq5�¥�§xºw ( =

��y%�§q5�Z�>wZ�vu�q,�/qB{®qz�¥x®��w sB��wUsBqz~��3#���w�q$szy!wSw��B� �/qVdUw�q ¿yB�×x�{£x®q5�n�! My!w1�§x��Õy!�v�v�!x��Ss^{®�.�T*��vq,�¥~Uy>sBq5�"=μwPqtyÌ�¥{)�%#b9U*��$x®wUy%�/q5�p*Uy!�vq%#Fy!�^�vq"�G~��¼�v���/�Õ�vu/x���x®w"�vqz�N�����B zsB��w:A�qVv � ( �dy!~�u u��p�G�%�G���^~�u/xs�z���szy!w 9UqZ ��%*�w@�+xºwS~®� � �K=�?�w q5�N�§qzwUsBq%#UqVvUsBqz~��, ������§�%�Gq��x)�G~/{®q%#FsB�%�<� ��w s^{®�.�T*��vq��¥~Uy�sBq5�t�T*Usvu"y%��(

Q:Ì

Page 28: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

x®w@�/qz~Uqzw@�/qzw/�5#b*�w��vqB{@y!�vq5�Õ~l�!x®w1�V�"#�����(��v���dy�{�{)�Õ�����/qz�vq5� ~U�Ìxºw/���"#À�vu�q¼{@y!�v�¥x@sBq�¥�v�7*UsB�N*��vq��B Y�>x �Fqz�vqzw/�s^{®�.�T*��vq��>~Uqz�dy!�^������y!~�~UqtyÌ�$�v��9Uq��%*/x®�vq�>x��¥�¥x®wUsB�5=\���>�qVvUyB�G~/{®q%#/{®qz�Z; sB��w@��x��¥�$�! �(�~U�!x®w/���\�$u/x@s^uuUy3A�qZy!w y!�79/xº�^�dy!�N�Õ~Uy!�v�¥x@yW{8�����/qz� � ��w��vu�q"��=�?�w ( qzw�qz�ByW{K#U�vu�q¼{@y!�^�¥x@sBq5�$�B � ;>FV���L�y!w@� � ;>F�� � �y!�vq>�%*/x®�vqS�>xs�§�¥x®wUsB�� c�v�p� � ;>FV� �Gy%�×��qB{�{ayp�Gqty�s^u ���vu�qz�5= p�u�q5�§q%#�x®w �N*��vw�#�yÌ�vqq�¥�^�N*UsB�N*��dyW{£{)��>x �Fqz�vqzw1�t ��v�%���vu�q�{ yÌ�v�¥x@sBqS�%9��dyWx®w�q5�>9:� sB��w@��x��/qz�¥x®w ( �^u�q×sB�>w.A�qVv ( qz�%�Gqz�v�N���! }�vu�q��vy!�GqS~U�!x®w/���~��v� <qtsB�vq5�Õ�>w1�v�ÕyS~/{@y!w�q%#@��u��.�¥q��§�v�N*UsB�N*��vqZ��*@�¥�»9Uq��>x �Fqz�vqzw/�, ��v�%� �vu�qSsB��w:A�qVv ( qz�%�Gqz�v�N� xI }�vu�q~U�Ìxºw/���»��qz�vq�~��v� ¥qtsB�vq5� x®w/�v� �!�K�¥~Uy>sBq%= � ?�w��vu�q5�¥qZ��q¼x)�G~/{£x@s^xº�§{�� y%�N�T*U�Gq5��y×X�*Us^{£x��/qty!w ( qz�%�Gqz�v�7��-���vu�qz� ( qz�%�Gqz�v�§xºq5�Â� y3�<��x®qB{������vu�qz��yÌw1�¥x)� yÌ�v�v�!x���s^{®�.�T*��vq��¥~Uy�sBq5�"=��pÔu�q5�¥q, �yB�Sx£{£x®q5�$�! ªs^{®�.�T*��vq¼{@y!�v�§x sBq5��y!�vqZ�%*/x®�vq¼x®w/�vqz�vq5�¥�¥x®w ( =�È q"��9lqz������x®�vu/x®w ��w�q» ¿y!�Sx£{��ÕuUy3A�q

��x)�Sx£{@y!�¥x®�¥x®q5�Z��u/x s^u �^qzw@���v���>x��¥�§xºw ( */xs�§u)�vu�q"�� c�v�p� � q"��9lqz�����B ÉyÌw����vu�qz�\ �yB�Sx£{)�%=��À����qVvÀyB� ~/{ºq%#xI ���q+szy�{�{�y ( qzw�qz�dyÌ�¥x®w ( �§qz�_>H��Òk�nLk��Tg5iBr %�r)j@�t�$u�qzwS_>H�� �h_>H���#Á�^u�qzw)xI Z_qH�� x��Sw���w����v�¥x)A>x@yW{x®wDy ~/{@y!wUy!�asB�>w.A�qVv ( qz�p�Gqz�v�N�%#�� _qH�� �1/ � -��$u/x£{®q�_>H��%w���w����v�¥x)A>x@yW{�xºw y �!�K�>x)�Gqzw@��x®��wUy�{�sB�>w.A�qVv( qz�%� qz�v�N�"qzw@�T*��vq5�K�vuUy!� � _>H��f� / � = p�u/x��SsvuUyÌ�dy�sB�vqz�¥x��¥�§x s��>x �Fqz�vqzwUsBqÕx��Z�By!�vu�qz�Z�p9.A>x®�%*@� -n���^u�qz����¥qzq"� �v�Z9Uqt�G���vq,�T*U9��§{ºq%=¡f)q�sB��w ¥qtsB�N*��vq¼�vuUy!�5#!qVvUsBqz~��� ����n�vu�q� �x®w@�U�:�B ]�¥~Uqts^x@yW{Fszy%�¥q5�¡�Gqzw1�§xº�>w�q5�yB9l��A>q%#t�vu�qz�^q}qVv/xs�§�Áw��Z�¥q"�Sx)�G�U�:*/{@y!�8{@y!�v�¥x@sBq�u��%�G�%� ���v~�u/x��T���0 ��v�%� s^{®�.�T*��vqÉ{@y!�v�¥x@sBq5�8�B ���w�q� �yB�Sx£{)��B }y!w/�¥x)� y!�v�v�Ìxs��s^{®�.�z*��vq��¥~Uy>sBq5����w/�v�S�vu�qZs^{®�.�T*��vq�{ yÌ�v�¥x@sBq5�$�! Éy!w��>�vu�qz�\ �yB�Sx£{)�%=

� � \� »�� � �

~®�$� U=���y!w! ®�$# U=��:�v�1�# ®�"# � =��yWx®�vw@�"# � = �y3A�x��"#Fy!w@� ��=�Æ��dy�sBq"�%= � w ¼q"A!y!w�q"��&��Z�/qVdUw/xº�§xº�>w5�B s^uUy!�.�"=�ªZÁ�254"Ã;1q¯%°¶¸®Ã;1>|%-@°¶¸:¬­²B#U�>� � � ��DÑ���%Q�� �>� � #BÎ�~��5=r�t���%QU=

~�Q!� !�:�¥qz~�uPX,=��:��w/x®w�# >yB�Gq5� � = � v/{ºq"�%#�y!w@�S�:�¥x ( x®�v�vq>Æ�qz�NA!y!�¥x)*@�"#nq5�>x®�v���V�"=)1q¯%°c4T|%/¶} ��¸.2V|%4�²B=�}�>w1�vq"� ~U���dyÌ�N��È"y!�vu�q"� yÌ�¥x@s"�"#�� �t�®Ì.=:Î��Gqz�3=®È"y!�^u�=@Æ���sB=)# �É�v�BA�x��/qzwUsBq%#3|\?�#8�t���pØU=

~Î�!�¢�:�vqzw@��y�É�= �x®qz�v�§x s^u�=È"y!�v�^�!x��U�$y!w@� Î�w/�¥x)� y!�^�v�!x��U��� ÎhÆ%*��NA�q"�b=Z/s68«34Ê23°c2 1q¯p°¶¸.25Á�¯%°c/¶«"6"#Ì�� D�Q%Q����UQ��:Ì.#��t�>���U=

~ � � �nyB*/{��'=]X��/qB{��Õy!w�=&È�qzqz�v�K�>x��¥�v�¥x)9U*��¥x)A�qÕ{@y!�v�§x sBq5�Sy!w@� �vu�q�y!w/�¥x®��qVvÀs^uUy!w ( q s^{®�.�T*��^q%=qªZ¬à³p2 . 4T¯��-@/¶15234N6"¯%¬I/)6"#U�3Ë � �:��D�Q��%Ë��®Q>���U#/�t���%ËU=

~�Ø!� �nyB*/{ �=UX��/qB{��Õy!w y!w@�Õ|��%9Uqz�^�ÂX»= �y!�Sx��¥��w�=ÁpÔu�qÏp�u�qz�>�N�G�B �}��w:A�qVv � qz�p�Gqz�v�¥x®q5�"=��,2�|%Á�2$¹°c4V/�¯p2 ¢2V}%/¶«�¯p°c¯%#F�t� � �:��D�Q � Ì��®Q:Ì�Ë:# ¼qtsB=F�W���%ØU=

~�¤!�¢È"y!�v�§xºw��ly!�N9lqz�ÔyÌw@��|��%9Uqz�^�ÂX»= �yB�Sx��¥��w�= �}��w:A�qVv1x®�T�Kx®w � �By!~�u@��y!w@� �»�/~Uqz� ( �By!~�u@�"=�Õ�*ʪ 1�@ÃbªZ¬à³%2 . 4T¯�¯p-@}�¢/s68«34T25°c2�1q23°¶¸.|5}B6"#0Ì � �:�VD � ����� � � � # B*/{)�)�t�>�%¤U=

~IÌ3� � y!�N� � �����/��w�= Î pL*��v�vq �8�!{)�1w��%�×x y�{� ���� �ny!�v�¥x@yW{£{)� � �V�/qz�vq5��Æ�qz���"=�� û|T´��W|%Á . /¶-@¯p°c|%4�/¶¯%¬��¸:2�|%4V²3Ö�Õ�234�/¶2"6��,#@Ø�� � �B��D®�W�%Q��M�"Ø%ØU#:Æ�qz~��3=F�t����� =

~Î�!� � qz��� ( q � �dy!�NÇzqz�5= ��-@/¶15234N6"¯%¬UªZ¬à³%2 . 4T¯%=��}y!w�g��.�¥�v�dyÌw@�b# �É�¥x®wUsBqz�v��w�#Hg #F�t�%¤�� =

Q��

Page 29: Computer Science | University of Virginia School of ...jlp/98.transform.pdf · ^uUy! ^u/x s ¼~UyÌ v ¥x@yW{n /qz ¥x®w ( B Q R x s $# lxºw ¿y sB 3# My × qB{ { § v N* UsB vq

~Î�!�¢�:qz�vw�uUy!�V� �¼�>�v�vq%#,ÉFy%�zÇB{º�PÉÃ��A!y%�TÇ%#¼y!w@� |$yWx®w�qz�>Æ1svu��By%�/qz�5= �,4T2V2�}p|%/�}!68= Æ�~��¥x®w ( qz�v� �nqz�¥{@y ( #�:qz�¥{£x®w�#n�t�����p=

~®�5Ë!�Æ1yB*�w@�/qz�V��È"y�s"ÉFyÌw�q%=wÆ��%�GqÕx®w/�vqz�v~��vqz�By!�¥x®��w@�S�B �yB9@�¥�v�dy>sB�Z{£x®w�qty!���/qz~Uqzw@�/qzwUsBq�x®w%�vqz�N���K�B ~��v� <qtsB�§x�A>q ( qz�%�Gqz�v�7��=�ªZÁ�254"à �@Ã�|T´�1>¯%°¶¸®Ãs#@Ø��UD�Q>�%Ø��®Q��®Ì.#��t���%¤ =

~®���$�¢�t=@È���w vy!���/qz�5=�ÎÏ*@�¥qt ����\ ��vq5�p*�qzw1�§{����^q5�>xs�^sB��A>qz�¥x®w ( yGsB��wUsBqz~��5= � 4T}%254V#3�%D � �3Ø�� � �5¤ #U�t���pØU=~®�5Q!� !�>u�wqÉ�= �Y ¿y�{º�7Ç%=WÆ�q"�×xº��u��p�G�%�G���^~�u/xs�z���$�! ¡�¥q"�×xº�c� �®�:*/{@y!��{@y!�v�¥x@sBq5�"=\Ô\4T|5«�Ã�|z´�ªZÁ�254"Ã;1q¯%°¶¸®Ã

Õb|5«�Ãs#@Q%Q � Q:��D � �t��� � Q%ØU#BÎt* ( =3�t�%¤>�U=~®�t�!� !�>u�w�É�= �� �yW{®�NÇ%= �}��w:A�qVv1x®�T��x®w��>x®�vqtsB�vq5� ( �dy!~�u@�"= � Ãb|z´�W|%Á . ÃZ��¸.2V|%4�²B#l�5Ë � Q:�VD®� � ���3�5¤%Q:#"μ~��5=�t�®Ì1�%=

~®� � � !�>u�w�É�= �� �yW{®�NÇ%=Fpr�dy!w@�y ����N� yÌ�¥x®��w@�8�B ��§�v�N*UsB�N*��vq5�¡9.�GsB��w:A�qVvGu��%�G�p�G���v~�u/x��T���$=@?�w �'=.XÉu��¥x ( #ÈS=!g�y ( {K#Uy!w@� � =�|��%Çzqzw:9Uqz� ( #�q5�>x®�v�����"# ��2V«5°c+:4T2��¢|p°c2"6Z/�- �W|%Á»{�+:°c254tÕb«5/¶25-0«�2$Ö�� ���� #�~Uy ( q5�Q��®Ì�� ���t� =UÆ�~��¥x®w ( qz�v� �nqz�§{ y ( #n�t����� =

~®�5Ø!� !�>u�w É¡=��� �yW{®�NÇ%=½X�A�y�{�*UyÌ�¥x®w ( �vu�q�9/x®wUy!�N�%~Uy!�v�§xº�§xº�>ww c*�wUsB�¥x®��w½�$u�qzw � � Q,*0= �W|p-.³%4T2$6�6�Z+.Á�234ʯp-@°c/¶+.Á�#8�5Ë��UDÎ� �M�5QU#��t�>�%ØU=

~®�5¤!� !�>u�wqÉ�= �Y ¿y�{º�7Ç%= �n{®�.�T*��vq�ÉFy!�v�§x sBq5�$= ¢/s6"«54T25°c2�1q¯p°¶¸.25Á�¯%°c/¶«"6"#F�5Ø � D�Q��BÌ��UQ��%¤U#/�t���%¤ =~®�BÌ3� �= =àÎ�= f)qB{��¥u�= 1q¯p°c4Ê|p/�}���¸:2�|%4V²B=�Î�szy%�/q"�Sx@s �É�vq5�N�"#3�t�:ÌB¤U=

Q��


Recommended