States and invariance in discrete mathematical structures and computing.

states-and-invariants.md

States and Invariants

• State: A state describes discrete change in the activity of a system on the physical electrical or the quantum level or the virtual level.
• Invariant: A predicate (or property) that is perserved for each state across the states chain under all state transitions; that is P(v) is true for all the members of the set of labeled arcs or in Automata Theory the set of delta functions $$\Delta$$ representing the state transitions in an Automaton.

Important

Theorems required to prove:

1. 

2. 

3. Steps to prove the theorem:

• Structural Definition:
  • Define a state space composed of the sequence tuple $$(V, A)$$; where $$V$$ represents the set of vertices, and $$A$$ represents the set of labeled arcs providing state transitions among the members of $$V$$.
  • A state space is a type of a Graph $$G (V, A)$$; where $$V$$ represents the set of vertices, and $$A$$ represents the set of edges connecting those vertices.
  • A labeled arc is a type of a graph edge that connects a vertex to its successor given an input $$\sigma$$.
  • $$\Sigma$$ represents the set of inputs that can be accepted by this state space (i.e., the alphabet of this state space).
  • $$\Sigma$$ set is closed under the closure operations; that is $$\Sigma^{*}$$ is a closure set under the original set $$\Sigma$$ defining the language accepted by a defined concrete state space object.
  • The set of labeled arcs $$A$$ is achieved through processing one of the closure operations under the $$\Sigma$$ set of inputs.
  • Second of all: Define the invariant property $$P(v)$$; that is a predicate that is perserved along the state transitions starting from the initial state $$v_0$$ along to the final state $$v_f$$.
  • The invariance principle defines an abstract predicate that is perserved along the state transitions which indicate a particular pattern for this state space that could be used to describe this state space (e.g., Recall a state space that keeps track of the number of digital input signals (signal a and signal b) by counting them; therefore there exists an invariant predicate that is true for each reachable state, this predicate could be something related to the input count, for example $$P(v) = (l == (m + n))$$; where $$l$$ is the total number of input signals, and $$m$$ is the number of signals of type a and $$n$$ is the number of signals of type b digital signals.
  • To prove the Invariance Principle of State Spaces, we have to show that; in an arbitrary state space $$X_s$$; for all transitions from a state to another, there exists a predicate that is always true $$\forall(v)\ \exists(P(v))$$, and this can be proved using mathematical induction.

Note

• Root argument for modular arithmetics: the following represents the root argument for modular arithmetics; the famous $$mod: (p, q) \rightarrow (p - (\lfloor{\frac{p}{q}\rfloor} \cdot q) )$$ which has a range of that results from an integer division operation using the $$p$$ as a divident and $$q$$ as the divisor. Justification can be made by a deductive or contrapositive argument.

References:

• States and Invariants: Essential Discrete Mathematics for Computer Science, Princeton University Press, ACM DL.
• Finite State Machines: Essential Discrete Mathematics for Computer Science, Princeton University Press, ACM DL.
• Switching and Finite Automata Theory, Cambridge Press.