MARC

 008260126s2024        us                              c    eng  d
■001000017360669
■00520260202105603
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798265402714
■035    ▼a(MiAaPQ)AAI32316034
■035    ▼a(MiAaPQ)GeorgiaTech76979
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a005
■1001  ▼aDing,  Shuo.
■24510▼aWitness  Functions  in  Program  Analysis  and  Complexity  Theory
■260    ▼a[Sl]▼bGeorgia  Institute  of  Technology▼c2024
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2024
■300    ▼a173  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-05,  Section:  B.
■500    ▼aAdvisor:  Zhang,  Qirun.
■5021  ▼aThesis  (Ph.D.)--Georgia  Institute  of  Technology,  2024.
■520    ▼aProving  impossibility  results  is  one  of  the  main  themes  of  program  analysis  theory  and  computability/complexity  theory.  For  example,  we  can  prove  a  program  analysis  problem  is  undecidable,  meaning  that  there  does  not  exist  an  algorithm  to  precisely  solve  the  problem.  As  another  example,  we  can  prove  a  problem  does  not  belong  to  a  complexity  class,  meaning  that  every  correct  algorithm  for  the  problem  must  exceed  the  given  resource  restriction.  In  general,  given  a  class  C  of  computational  problems  and  a  specific  computational  problem  P  not  in  C,  a  witness  function  maps  every  candidate  Q  in  C  to  an  input  on  which  P  and  Q  are  different.We  investigate  the  computational  properties  of  such  witness  functions  and  discuss  their  implications.  In  program  analysis  theory,  we  prove  that  a  large  class  of  undecidable  program  analysis  problems  have  computable  witness  functions,  including  every  semantic  property  described  in  Rice's  theorem.  This  implies  the  existence  of  computable  functions  mapping  every  program  analyzer  to  a  more  precise  program  analyzer.  Through  two  real  program  analysis  tasks  (1)  CFL-reachability  based  program  analysis  for  Java  and  LLVMIR  and  (2)  template  constraint  analysis  for  C++,  we  demonstrate  that  computable  witness  functions  provide  guarantees  on  the  progress  of  developing  more  and  more  precise  program  analysis  techniques.  In  complexity  theory,  we  prove  that  witness  functions  for  major  complexity  classes  are  closely  related  to  reductions,  and  discuss  the  implications  in  complexity  class  separation  proofs.
■590    ▼aSchool  code:  0078.
■650  4▼aProgramming  languages
■650  4▼aC  plus  plus
■650  4▼aComplexity  theory
■650  4▼aSemantics
■650  4▼aComputer  science
■690    ▼a0984
■71020▼aGeorgia  Institute  of  Technology.
■7730  ▼tDissertations  Abstracts  International▼g87-05B.
■790    ▼a0078
■791    ▼aPh.D.
■792    ▼a2024
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360669▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books