חדשות והודעות הפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

ברכות חמות לגיא ארבל, סטודנט לדוקטורט בפקולטה, על זכייתו בפרס המאמר המצטיין (Distinguished Paper Award) בכנס LICS - מהכנסים המובילים והיוקרתיים בתחום הלוגיקה במדעי המחשב.

המאמר "A Complexity Bound for Determinisation of Min-Plus Weighted Automata" עוסק בסיבוכיות של בעיית הדטרמניזציה של אוטומטים ממושקלים, מודל חישובי מרכזי. סוגיית הכריעות של בעייה זו היתה פתוחה למעלה מ-30 שנה, עד שהוכחה ככריעה בעבודה פורצת דרך קודמת של גיא.

בעבודה הנוכחית, גיא, יחד עם מנחיו, פרופ' שאול אלמגור וד"ר שרי שינולד, העמיק את ההישג ומצא חסם סיבוכיות לבעיה. מעבר לתוצאה החשובה, גיא פיתח במהלך העבודה טכניקות חדשות ומקוריות להתמודדות עם אוטומטים ממושקלים, שישמשו את הקהילה החוקרת את התחום.

כל הכבוד על ההישג המרשים!!

למאמר המלא: https://arxiv.org/pdf/2602.01221

לאתר הכנס: https://lics.siglog.org/lics26/