Model Checking Syllabi and Student Carreers

Roberto Sebastiani, Alessandro Tomasi, Fausto Giunchiglia

Abstract

The transition to flexible, credit-based university systems has introduced significant complexity for students planning their careers and for administrators verifying degree coherence. This paper presents a formal methods approach to these challenges, treating student careers as finite state machines and graduation requirements as logic formulas. Using the SMV symbolic model checker and specific state-space optimization techniques, the authors demonstrate that automated career synthesis and syllabus verification are not only possible but efficient, even for large-scale degree programs.

Introduction: The Combinatorial Challenge of Modern Degrees

In the early 2000s, the Italian university system shifted from a rigid structure to a flexible, credit-based model. While this offered students more choice, it introduced a "combinatorial nightmare" of regulations involving subject areas, credit minimums/maximums, and strict prerequisites. This paper addresses two primary problems: Career Synthesis, which involves finding a valid path to graduation for a student, and Syllabus Coherence Verification, which ensures a university's course offerings allow all students to reach a graduation state without hitting dead ends.

Methodology: Careers as State Machines

The core of the proposed solution is modeling a student's academic progress as a Finite State Machine (FSM). In this model, each state represents a snapshot of a student's career, including the set of courses completed, the current matriculation year, and accumulated credits. Transitions between states occur when a student passes an exam or completes a milestone like a thesis.

Figure 1: Modeling student careers as a Finite State Machine (FSM), where states represent sets of completed courses.

Graduation requirements are then encoded as Computation Tree Logic (CTL) formulas. For instance, a requirement to earn at least 180 credits is treated as a goal state property that the model checker must reach.

Formalizing Bureaucracy

To make the system functional, "soft" human regulations must be translated into "hard" formal constraints. These rules often involve complex intersections of subject areas (e.g., MAT01, INF01) and activity types (e.g., courses, thesis, internships).

Figure 2: Formal representation of graduation requirements as a set of rules (r1-r8) with specific credit and subject area constraints.

Optimization and Performance

The state space for a typical degree program is massive, often exceeding the memory limits of standard model checkers like SMV. The authors introduced three critical optimization "tricks" to handle this:

  1. GCD Reduction: Dividing all credit values by their greatest common divisor (e.g., 5) to shrink the numerical range the model checker tracks.
  2. State Restriction: Prioritizing mandatory courses to reduce non-deterministic choices that bloat the search space.
  3. Rule Merging: Combining similar constraints into single counters where possible.

Testing these methods on Mathematics and Physics syllabi from the University of Trento showed dramatic results. For the Mathematics syllabus, verification time dropped from failing (due to memory exhaustion) to just 40 seconds with all optimizations active. Career synthesis—finding a single valid path—was nearly instantaneous, typically taking under two seconds.

Conclusion and Future Directions

This research demonstrates that formal verification tools, typically reserved for hardware and software engineering, are highly effective for managing complex administrative systems. While the current model assumes a static syllabus, future work aims to incorporate temporal changes in course offerings and better handle "OR" constraints where one activity might satisfy multiple different credit categories. By formalizing bureaucracy, universities can provide students with better planning tools and ensure their degree programs remain navigable.

Summary updated

Abstract

Model checking has been conceived as a powerful tool for hardware, software and protocol verification, which has its main application fields in the development of hi-tech and safety-critical systems. We present here a completely novel application in the field of university administration processes, in which model checking is applied to the verification of the coherence of syllabi and to the automated synthesis/simulation of correct student careers under given requirements.
BibTeX
@inproceedings{sebastiani2001model,
  author = {Roberto Sebastiani and Alessandro Tomasi and Fausto Giunchiglia},
  title = {{Model Checking Syllabi and Student Carreers}},
  booktitle = {TACAS},
  year = {2001},
  doi = {10.1007/3-540-45319-9\_10},
}
Figure