module Pbword: sig .. end
Naive implementation of ultimately Periodic Binary Words.
Author(s): Louis Mandel, Florence Plateau
Data structures
type bool list
Finite word:
u ::= epsilon | 0u | 1v.
type
}
Ultimately Periodic Binary Words:
p ::= u(v).
val one : periodic_binary_word
The ultimately periodic binary word (1).
Functions on ultimately periodic binary words
val size : 'a list -> int
Size of a finite word u:
|u|.
val nbones : bool list -> int
Number of 1s a finite word u:
|u|_1.
val iof : periodic_binary_word -> int -> int
Index of the jth 1 of an ultimately periodic binary word p:
I_p(j).
val increase_prefix : periodic_binary_word -> int -> periodic_binary_word
Increase prefix size of n bits:
u(vv') = uv(v'v) with |v| = n.
val repeat_periodic_pattern : periodic_binary_word -> int -> periodic_binary_word
Repeat periodic pattern: u(v) = u(v^k).
val rate : periodic_binary_word -> int * int
Computation of the rate of an ultimately periodic binary word:
rate p = |p.v|_1 / |p.v|.
val (|><|) : periodic_binary_word -> periodic_binary_word -> bool
The synchronizability test of two ultimately periodic binary words:
p_1 |><| p_2 <=> rate p1 = rate p2.
val prece : periodic_binary_word -> periodic_binary_word -> bool
The precedence test of two ultimately periodic binary words:
p_1 <= p_2 <=> I_{p_1}(j) <= I_{p_2}(j),
for all 1 <= j <= h
with h = max (|p_1.u|_1,|p_2.u|_1) + lcm (|p_1.v|_1,|p_2.v|_1).
val (<:) : periodic_binary_word -> periodic_binary_word -> bool
The adaptability test of two ultimately periodic binary words:
p_1 <: p_2.
val on : periodic_binary_word ->
periodic_binary_word -> periodic_binary_word
Computation of the on operator:
u_3(v_3) = u_1(v_1) on u_2(v_2)
with |u_3| = max (|u_1|, I_{p_1}(|u_2|)),
|v_3| = (lcm (|v_1|_1, |v_2|) / |v_1|_1) * |v_1|
and for all 1 <= i <= |u_3|, u_3[i] = (p_1 on p_2)[i]
and for all 1 <= i <= |v_3|, v_3[i] = (p_1 on p_2)[|u_3| + i]
Printing functions
val fprint_bool : Format.formatter -> bool -> unit
val fprint_word : Format.formatter -> bool list -> unit
val fprint_pbw : Format.formatter -> periodic_binary_word -> unit