Require Export prosa.behavior.ready.
Notation "[ rel _ _ | _ ]" was already used in scope
fun_scope. [notation-overridden,parsing]
Notation "[ rel _ _ : _ | _ ]" was already used in
scope fun_scope. [notation-overridden,parsing]
Notation "[ rel _ _ in _ & _ | _ ]" was already used
in scope fun_scope. [notation-overridden,parsing]
Notation "[ rel _ _ in _ & _ ]" was already used in
scope fun_scope. [notation-overridden,parsing]
Notation "[ rel _ _ in _ | _ ]" was already used in
scope fun_scope. [notation-overridden,parsing]
Notation "[ rel _ _ in _ ]" was already used in scope
fun_scope. [notation-overridden,parsing]
Notation "_ + _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation "_ - _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation "_ <= _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation "_ < _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation "_ >= _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation "_ > _" was already used in scope nat_scope.
[notation-overridden,parsing]
Notation "_ <= _ <= _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation "_ < _ <= _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation "_ <= _ < _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation "_ < _ < _" was already used in scope
nat_scope. [notation-overridden,parsing]
Notation "_ * _" was already used in scope nat_scope.
[notation-overridden,parsing]
Require Export prosa.util.nat.

(** We define the notion of prefix-equivalence of schedules. *)

Section PrefixDefinition.

  (** For any type of jobs... *)
  Context {Job : JobType}.

  (** ... and any kind of processor model, ... *)
  Context {PState: Type} `{ProcessorState Job PState}.

  (** ... two schedules share an identical prefix if they are pointwise
          identical (at least) up to a fixed horizon. *)
  Definition identical_prefix (sched sched' : schedule PState) (horizon : instant) :=
    forall t,
      t < horizon ->
      sched t = sched' t.

  (** In other words, two schedules with a shared prefix are completely
      interchangeable w.r.t. whether a job is scheduled (in the prefix). *)
  Fact identical_prefix_scheduled_at:
    forall sched sched' h,
      identical_prefix sched sched' h ->
      forall j t,
        t < h ->
        scheduled_at sched j t = scheduled_at sched' j t.
Job: JobType
PState: Type
H: ProcessorState Job PState
forall (sched sched' : schedule PState) (h : instant),
identical_prefix sched sched' h ->
forall (j : Job) (t : nat),
t < h ->
scheduled_at sched j t = scheduled_at sched' j t
  Proof.
Job: JobType
PState: Type
H: ProcessorState Job PState
forall (sched sched' : schedule PState) (h : instant),
identical_prefix sched sched' h ->
forall (j : Job) (t : nat),
t < h ->
scheduled_at sched j t = scheduled_at sched' j t
    move=> sched sched' h IDENT j t LT_h.
Job: JobType
PState: Type
H: ProcessorState Job PState
sched, sched': schedule PState
h: instant
IDENT: identical_prefix sched sched' h
j: Job
t: nat
LT_h: t < h
scheduled_at sched j t = scheduled_at sched' j t
    now rewrite /scheduled_at (IDENT t LT_h).
  Qed.

  (** Trivially, any prefix of an identical prefix is also an identical
      prefix. *)
  Fact identical_prefix_inclusion:
    forall sched sched' h,
      identical_prefix sched sched' h ->
      forall h',
        h' <= h ->
        identical_prefix sched sched' h'.
Job: JobType
PState: Type
H: ProcessorState Job PState
forall (sched sched' : schedule PState) (h : instant),
identical_prefix sched sched' h ->
forall h' : nat,
h' <= h -> identical_prefix sched sched' h'
  Proof.
Job: JobType
PState: Type
H: ProcessorState Job PState
forall (sched sched' : schedule PState) (h : instant),
identical_prefix sched sched' h ->
forall h' : nat,
h' <= h -> identical_prefix sched sched' h'
    move=> sched sched' h IDENT h' INCL t LT_h'.
Job: JobType
PState: Type
H: ProcessorState Job PState
sched, sched': schedule PState
h: instant
IDENT: identical_prefix sched sched' h
h': nat
INCL: h' <= h
t: nat
LT_h': t < h'
sched t = sched' t
    apply IDENT.
Job: JobType
PState: Type
H: ProcessorState Job PState
sched, sched': schedule PState
h: instant
IDENT: identical_prefix sched sched' h
h': nat
INCL: h' <= h
t: nat
LT_h': t < h'
t < h
    now apply (ltn_leq_trans LT_h').
  Qed.

End PrefixDefinition.