(*
Autor(s):
Andrej Dudenhefner (1)
Affiliation(s):
(1) Saarland University, Saarbrücken, Germany
*)
(*
Confluence, boundedness, length preserving transformations
- Modules AddFreshLoop, AddFreshLoop': add rules aX <-> X'b where X' is fresh
- Module DerivableRule: add derivable rule / removing redundant rule
- Module DerivableRule': add rule that is derivable with a prefix
- Module Reordering: change order, duplicate rules
*)
Require Import List Lia.
Import ListNotations.
Require Import Relation_Operators Operators_Properties.
Require Import Undecidability.StackMachines.SMN.
Require Undecidability.StackMachines.SSM.
From Undecidability.StackMachines.Util Require Import Nat_facts List_facts SMN_facts.
Require Import Undecidability.StackMachines.Util.SMN_transform.
Require Import ssreflect ssrbool ssrfun.
Set Default Proof Using "Type".
Set Default Goal Selector "!".
Module Argument.
Section Reduction.
Variable M : SMN.
Variable confluent_M : confluent M.
Variable basic_M : Forall basic M.
Definition encode_Instruction (op: Instruction) : SSM.instruction :=
match op with
| (([], [a], x), ([b], [], y)) => (x, y, a, b, false)
| (([a], [], x), ([], [b], y)) => (x, y, a, b, true)
| _ => (0, 0, true, true, true)
end.
Definition M' : SSM.ssm := map encode_Instruction M.
Lemma basic_instructions : forall op, In op M -> basic op.
Proof using basic_M. by apply /Forall_forall. Qed.
Lemma simulation_step {x y} : step M x y -> SSM.step M' x y.
Proof using basic_M.
case=> v w l r l' r' {}x {}y Hop. move: Hop (Hop) => /basic_instructions.
move H1op: (l, r, x, (l', r', y)) => op H2op. case: H2op H1op.
- move=> > [] *. subst. apply: SSM.step_r. rewrite /M' in_map_iff. eexists. by constructor; last by eassumption.
- move=> > [] *. subst. apply: SSM.step_l. rewrite /M' in_map_iff. eexists. by constructor; last by eassumption.
Qed.
Lemma simulation {x y} : reachable M x y -> SSM.reachable M' x y.
Proof using basic_M.
elim.
- move=> ? ? /simulation_step ?. by apply: rt_step.
- move=> *. by apply: rt_refl.
- move=> *. apply: rt_trans; by eassumption.
Qed.
Lemma inverse_simulation_step {x y} : SSM.step M' x y -> step M x y.
Proof using basic_M.
case=> >.
- rewrite /M' in_map_iff. move=> [[[[l r] {}x] [[l' r'] {}y]]] [] + HM.
move: HM (HM) => /basic_instructions.
move H1op: (l, r, x, (l', r', y)) => op H2op. case: H2op H1op.
+ move=> > /=. by congruence.
+ move=> > [] /= ? ? ? ? ? ? + [] *. subst. move /transition. by apply.
- rewrite /M' in_map_iff. move=> [[[[l r] {}x] [[l' r'] {}y]]] [] + HM.
move: HM (HM) => /basic_instructions.
move H1op: (l, r, x, (l', r', y)) => op H2op. case: H2op H1op.
+ move=> > [] /= ? ? ? ? ? ? + [] *. subst. move /transition. by apply.
+ move=> > /=. by congruence.
Qed.
Lemma inverse_simulation {x y} : SSM.reachable M' x y -> reachable M x y.
Proof using basic_M.
elim.
- move=> ? ? /inverse_simulation_step ?. by apply: rt_step.
- move=> *. by apply: rt_refl.
- move=> *. apply: rt_trans; by eassumption.
Qed.
Lemma confluent_M' : SSM.confluent M'.
Proof using basic_M confluent_M.
move=> ? ? ? /inverse_simulation /= H1 /inverse_simulation /= H2.
have [? []] := confluent_M _ _ _ H1 H2.
move=> /simulation /= ? /simulation /= ?.
eexists. constructor; by eassumption.
Qed.
Lemma boundedness : (exists NM, bounded M NM) <-> (exists NM', SSM.bounded M' NM').
Proof using basic_M.
constructor.
- move=> [NM bounded_M]. exists NM.
move=> X. have [L [HL ?]] := bounded_M X.
exists L. constructor; last done.
by move=> ? /inverse_simulation /= /HL ?.
- move=> [NM' bounded_M']. exists NM'.
move=> X. have [L [HL ?]] := bounded_M' X.
exists L. constructor; last done.
by move=> ? /simulation /= /HL ?.
Qed.
End Reduction.
End Argument.
Require Import Undecidability.Synthetic.Definitions.
(* compute from a deterministic, length-preserving SMN a confluent simple stack machine *)
Local Definition SMNdl_to_cssm : { M : SMN | deterministic M /\ length_preserving M } -> SSM.cssm.
Proof.
move=> [M [/deterministic_confluent H1M H2M]].
exists (Argument.M' (sval (construct_basic_SMN M H1M H2M))).
apply: Argument.confluent_M'.
- exact (fst (snd (svalP (construct_basic_SMN M H1M H2M)))).
- exact (fst ((svalP (construct_basic_SMN M H1M H2M)))).
Defined.
(* many-one reduction from deterministic, length-preserving stack machine uniform boundedness to confluent simple stack machine uniform boundedness *)
Theorem reduction : SMNdl_UB ⪯ SSM.CSSM_UB.
Proof.
exists SMNdl_to_cssm. move=> [M [H1M H2M]]. constructor.
- move=> [nMN] /=.
set M1 := (construct_basic_SMN M (deterministic_confluent H1M) H2M).
move=> HM. have [? [?]] := svalP M1.
move /iffLR => /(_ ltac:(by eexists)) => /Argument.boundedness. by apply.
- move /Argument.boundedness. set M1 := (construct_basic_SMN M (deterministic_confluent H1M) H2M).
have [? [? <-]] := svalP M1. by apply.
Qed.
Autor(s):
Andrej Dudenhefner (1)
Affiliation(s):
(1) Saarland University, Saarbrücken, Germany
*)
(*
Confluence, boundedness, length preserving transformations
- Modules AddFreshLoop, AddFreshLoop': add rules aX <-> X'b where X' is fresh
- Module DerivableRule: add derivable rule / removing redundant rule
- Module DerivableRule': add rule that is derivable with a prefix
- Module Reordering: change order, duplicate rules
*)
Require Import List Lia.
Import ListNotations.
Require Import Relation_Operators Operators_Properties.
Require Import Undecidability.StackMachines.SMN.
Require Undecidability.StackMachines.SSM.
From Undecidability.StackMachines.Util Require Import Nat_facts List_facts SMN_facts.
Require Import Undecidability.StackMachines.Util.SMN_transform.
Require Import ssreflect ssrbool ssrfun.
Set Default Proof Using "Type".
Set Default Goal Selector "!".
Module Argument.
Section Reduction.
Variable M : SMN.
Variable confluent_M : confluent M.
Variable basic_M : Forall basic M.
Definition encode_Instruction (op: Instruction) : SSM.instruction :=
match op with
| (([], [a], x), ([b], [], y)) => (x, y, a, b, false)
| (([a], [], x), ([], [b], y)) => (x, y, a, b, true)
| _ => (0, 0, true, true, true)
end.
Definition M' : SSM.ssm := map encode_Instruction M.
Lemma basic_instructions : forall op, In op M -> basic op.
Proof using basic_M. by apply /Forall_forall. Qed.
Lemma simulation_step {x y} : step M x y -> SSM.step M' x y.
Proof using basic_M.
case=> v w l r l' r' {}x {}y Hop. move: Hop (Hop) => /basic_instructions.
move H1op: (l, r, x, (l', r', y)) => op H2op. case: H2op H1op.
- move=> > [] *. subst. apply: SSM.step_r. rewrite /M' in_map_iff. eexists. by constructor; last by eassumption.
- move=> > [] *. subst. apply: SSM.step_l. rewrite /M' in_map_iff. eexists. by constructor; last by eassumption.
Qed.
Lemma simulation {x y} : reachable M x y -> SSM.reachable M' x y.
Proof using basic_M.
elim.
- move=> ? ? /simulation_step ?. by apply: rt_step.
- move=> *. by apply: rt_refl.
- move=> *. apply: rt_trans; by eassumption.
Qed.
Lemma inverse_simulation_step {x y} : SSM.step M' x y -> step M x y.
Proof using basic_M.
case=> >.
- rewrite /M' in_map_iff. move=> [[[[l r] {}x] [[l' r'] {}y]]] [] + HM.
move: HM (HM) => /basic_instructions.
move H1op: (l, r, x, (l', r', y)) => op H2op. case: H2op H1op.
+ move=> > /=. by congruence.
+ move=> > [] /= ? ? ? ? ? ? + [] *. subst. move /transition. by apply.
- rewrite /M' in_map_iff. move=> [[[[l r] {}x] [[l' r'] {}y]]] [] + HM.
move: HM (HM) => /basic_instructions.
move H1op: (l, r, x, (l', r', y)) => op H2op. case: H2op H1op.
+ move=> > [] /= ? ? ? ? ? ? + [] *. subst. move /transition. by apply.
+ move=> > /=. by congruence.
Qed.
Lemma inverse_simulation {x y} : SSM.reachable M' x y -> reachable M x y.
Proof using basic_M.
elim.
- move=> ? ? /inverse_simulation_step ?. by apply: rt_step.
- move=> *. by apply: rt_refl.
- move=> *. apply: rt_trans; by eassumption.
Qed.
Lemma confluent_M' : SSM.confluent M'.
Proof using basic_M confluent_M.
move=> ? ? ? /inverse_simulation /= H1 /inverse_simulation /= H2.
have [? []] := confluent_M _ _ _ H1 H2.
move=> /simulation /= ? /simulation /= ?.
eexists. constructor; by eassumption.
Qed.
Lemma boundedness : (exists NM, bounded M NM) <-> (exists NM', SSM.bounded M' NM').
Proof using basic_M.
constructor.
- move=> [NM bounded_M]. exists NM.
move=> X. have [L [HL ?]] := bounded_M X.
exists L. constructor; last done.
by move=> ? /inverse_simulation /= /HL ?.
- move=> [NM' bounded_M']. exists NM'.
move=> X. have [L [HL ?]] := bounded_M' X.
exists L. constructor; last done.
by move=> ? /simulation /= /HL ?.
Qed.
End Reduction.
End Argument.
Require Import Undecidability.Synthetic.Definitions.
(* compute from a deterministic, length-preserving SMN a confluent simple stack machine *)
Local Definition SMNdl_to_cssm : { M : SMN | deterministic M /\ length_preserving M } -> SSM.cssm.
Proof.
move=> [M [/deterministic_confluent H1M H2M]].
exists (Argument.M' (sval (construct_basic_SMN M H1M H2M))).
apply: Argument.confluent_M'.
- exact (fst (snd (svalP (construct_basic_SMN M H1M H2M)))).
- exact (fst ((svalP (construct_basic_SMN M H1M H2M)))).
Defined.
(* many-one reduction from deterministic, length-preserving stack machine uniform boundedness to confluent simple stack machine uniform boundedness *)
Theorem reduction : SMNdl_UB ⪯ SSM.CSSM_UB.
Proof.
exists SMNdl_to_cssm. move=> [M [H1M H2M]]. constructor.
- move=> [nMN] /=.
set M1 := (construct_basic_SMN M (deterministic_confluent H1M) H2M).
move=> HM. have [? [?]] := svalP M1.
move /iffLR => /(_ ltac:(by eexists)) => /Argument.boundedness. by apply.
- move /Argument.boundedness. set M1 := (construct_basic_SMN M (deterministic_confluent H1M) H2M).
have [? [? <-]] := svalP M1. by apply.
Qed.