ปัญหาการไม่ว่างเปล่าของจุดตัดหรือที่รู้จักกันในชื่อปัญหาจุดตัดของออโตมาตาจำกัด^{[ 1 ]}หรือปัญหาการไม่ว่างเปล่าของจุดตัดเป็น ปัญหาการตัดสินใจ ที่สมบูรณ์แบบ PSPACEจากสาขาทฤษฎีออโตมาตาปัญหานี้ถามว่ารายการของออโตมาตาจำกัดแบบกำหนดมีจุดตัดที่ไม่ว่างเปล่าหรือไม่

ปัญหาการตัดสินใจที่ไม่ว่างเปล่าถูกกำหนด (สำหรับออโตมาตอนประเภทหนึ่งโดยเฉพาะ) ดังนี้: เมื่อกำหนดออโตมาตอนเป็นอินพุต เป้าหมายคือการพิจารณาว่าภาษาของออโตมาตอนไม่ว่างเปล่าหรือไม่ กล่าวคือ มีสตริงที่ออโตมาตอนยอมรับหรือไม่ ปัญหาที่ไม่ว่างเปล่าได้รับการศึกษาในสาขาทฤษฎีออโตมาตามาหลายปี ปัญหาที่ไม่ว่างเปล่าทั่วไปหลายปัญหาได้รับการพิสูจน์แล้วว่าสมบูรณ์สำหรับคลาสความซับซ้อนตั้งแต่^{Deterministic} LogspaceจนถึงPSPACE [ ^{2 ]}

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

มี อัลกอริทึม เวลาเลขชี้กำลังที่แก้ปัญหาความไม่ว่างเปล่าของการตัดกันโดยอาศัยการสร้างผลคูณคาร์ทีเซียน ที่แนะนำโดย Michael O. RabinและDana Scott [ ^{3 ] แนวคิด} คือออโตมาตาทั้งหมดรวมกันเป็น "ออโตมาตาผลคูณ" ซึ่งสถานะประกอบด้วยทูเปิลของสถานะในรายการของออโตมาตา สตริงจะได้รับการยอมรับโดยออโตมาตาผลคูณก็ต่อเมื่อได้รับการยอมรับโดยทุกออโตมาตาในรายการเท่านั้น ดังนั้นการค้นหาแบบกว้าง (หรือการค้นหาแบบลึก ) ภายในพื้นที่สถานะของออโตมาตาผลคูณจะกำหนดว่ามีเส้นทางจากสถานะเริ่มต้นของผลคูณไปยังสถานะสุดท้ายของผลคูณหรือไม่ การมีหรือไม่มีเส้นทางดังกล่าวเทียบเท่ากับการกำหนดว่าสตริงใดได้รับการยอมรับโดยทุกออโตมาตาในรายการหรือไม่

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

ปัญหาจุดตัดที่ไม่ว่างเปล่าได้รับการพิสูจน์แล้วว่าเป็นปัญหาPSPACE-completeโดยDexter Kozenในปี 1977 ^{[ 1 ]}ยังคงเป็นปัญหาที่ยังไม่ได้รับการแก้ไขว่ามีอัลกอริทึมที่เร็วกว่านี้หรือไม่^{[ 4 ]}

• ออโตมาตาจำกัดเชิงกำหนด
• ปัญหาความว่างเปล่า
• PSPACE-เสร็จสมบูรณ์
• รายชื่อปัญหาที่แก้ไขได้ด้วยวิธี PSPACE