ตรรกะเชิงเวลาและเชิงกิริยาในการคำนวณ

ตรรกะเชิงเวลาและเชิงกิริยาขยายตรรกะคลาสสิกด้วยตัวดำเนินการสำหรับเวลาและความเป็นไปได้ ทำให้เกิดภาษาที่แม่นยำในการระบุว่าโปรแกรมหรือระบบเชิงโต้ตอบจะต้องทำงานอย่างไรตลอดการประมวลผลทั้งหมด

Definition

ตรรกะเชิงเวลาเพิ่มตรรกะเชิงประพจน์หรือตรรกะอันดับหนึ่งด้วยตัวดำเนินการที่อธิบายว่าคุณสมบัติเป็นจริงเมื่อใดตลอดการคำนวณ เช่น เสมอ, ในที่สุด, และจนกว่า; ตรรกะเชิงกิริยาทำให้สิ่งนี้เป็นสากลมากขึ้นด้วยตัวดำเนินการสำหรับความจำเป็นและความเป็นไปได้เหนือโครงสร้างของสถานะและการเปลี่ยนผ่าน

Scope

หัวข้อนี้ครอบคลุมตรรกะเชิงเวลาแบบเส้นตรงและแบบแตกแขนง เช่น LTL และ CTL, ตรรกะเชิงกิริยา รวมถึงตรรกะพลวัตและโมดัลมิว-แคลคูลัส, การแสดงคุณสมบัติความปลอดภัยและคุณสมบัติความมีชีวิตชีวา, และปัญหาเชิงอัลกอริทึมของการตรวจสอบแบบจำลองและความน่าพอใจ ซึ่งทำให้ตรรกะเหล่านี้มีความสำคัญต่อการตรวจสอบอัตโนมัติ

Core questions

• ตรรกะสามารถแสดงได้อย่างไรว่าสิ่งที่ดีจะเกิดขึ้นในที่สุด หรือสิ่งที่ไม่ดีจะไม่เกิดขึ้นเลย?
• อะไรคือความแตกต่างระหว่างการให้เหตุผลเกี่ยวกับการประมวลผลครั้งเดียวกับการให้เหตุผลเกี่ยวกับอนาคตที่เป็นไปได้ทั้งหมด?
• การตรวจสอบว่าระบบเป็นไปตามคุณสมบัติเชิงเวลาได้อย่างไรจึงจะกลายเป็นอัลกอริทึม?
• ตรรกะเชิงเวลาใดที่สร้างสมดุลระหว่างพลังการแสดงออกกับการตรวจสอบที่มีประสิทธิภาพ?

Key theories

ตรรกะเชิงเวลาสำหรับการระบุคุณสมบัติของโปรแกรม

Pnueli แสดงให้เห็นว่าตรรกะเชิงเวลาสามารถจับความถูกต้องของโปรแกรมเชิงโต้ตอบและโปรแกรมพร้อมกันได้โดยการแสดงคุณสมบัติเหนือการทำงานของโปรแกรมเหล่านั้น ซึ่งเป็นภาษาที่เป็นหนึ่งเดียวสำหรับข้อกำหนดด้านความปลอดภัยและความมีชีวิตชีวา

การตรวจสอบแบบจำลองตรรกะเชิงเวลาแบบแตกแขนง

Clarke และ Emerson ได้นำเสนอ Computation Tree Logic และอัลกอริทึมเพื่อตรวจสอบโดยอัตโนมัติกับแบบจำลองสถานะจำกัด ซึ่งเป็นรากฐานของสาขาการตรวจสอบแบบจำลอง

Clinical relevance

ตรรกะเชิงเวลาเป็นภาษาที่ใช้ในการระบุคุณสมบัติของตัวตรวจสอบแบบจำลองที่ใช้เป็นประจำเพื่อตรวจสอบการออกแบบฮาร์ดแวร์, โปรโตคอลการสื่อสาร, และซอฟต์แวร์พร้อมกัน, เพื่อตรวจจับภาวะชะงักงันและการละเมิดความปลอดภัยและความมีชีวิตชีวาก่อนการนำไปใช้งาน; เทคโนโลยีนี้ทำให้ผู้ริเริ่มได้รับรางวัล Turing Award และเป็นมาตรฐานในการออกแบบชิป

History

Pnueli เสนอแนวคิดตรรกะเชิงเวลาสำหรับการให้เหตุผลเกี่ยวกับโปรแกรมในปี 1977 และ Clarke กับ Emerson ร่วมกับ Queille และ Sifakis ได้พัฒนาการตรวจสอบแบบจำลองโดยอิสระประมาณปี 1981 แนวทางนี้ได้ขยายไปสู่ระบบอุตสาหกรรมผ่านวิธีการเชิงสัญลักษณ์ในช่วงต้นทศวรรษ 1990 และผู้สร้างได้รับรางวัล Turing Award สำหรับเทคนิคนี้

Key figures

• Amir Pnueli
• Edmund Clarke
• E. Allen Emerson
• Joseph Sifakis

Seminal works

• clarkeEmerson1981
• huthRyan2004

Frequently asked questions

อะไรคือความแตกต่างระหว่างตรรกะเชิงเวลาแบบเส้นตรงและแบบแตกแขนง?

ตรรกะเชิงเวลาแบบเส้นตรง เช่น LTL อธิบายคุณสมบัติของเส้นทางการทำงานเดียวที่อาจไม่มีที่สิ้นสุด ตรรกะเชิงเวลาแบบแตกแขนง เช่น CTL จะหาปริมาณเหนือต้นไม้ของอนาคตที่เป็นไปได้ทั้งหมดจากแต่ละสถานะ ทำให้สามารถกล่าวได้ว่าตามเส้นทางบางเส้นทางหรือตามเส้นทางทั้งหมด คุณสมบัติเป็นจริง ตรรกะทั้งสองมีพลังการแสดงออกและอัลกอริทึมการตรวจสอบที่แตกต่างกัน

การตรวจสอบแบบจำลองใช้ตรรกะเหล่านี้อย่างไร?

ระบบจะถูกแสดงเป็นแบบจำลองสถานะจำกัด และคุณสมบัติที่ต้องการจะถูกแสดงเป็นสูตรตรรกะเชิงเวลา ตัวตรวจสอบแบบจำลองจะสำรวจสถานะทั้งหมดเพื่อพิจารณาว่าสูตรเป็นจริงหรือไม่ และหากล้มเหลวก็จะสร้างร่องรอยตัวอย่างที่ขัดแย้ง ทำให้การตรวจสอบเป็นไปโดยอัตโนมัติและสามารถวินิจฉัยได้