PaperlayerView exact revision on arXiv

Source-linked AI summary

Observability of Boolean control networks: A unified approach based on the theories of finite automata

Kuize Zhang, Lijun Zhang

arXiv:1405.6780v2math.OC

TL;DR

The paper addresses the unresolved problem of determining four observability notions for Boolean control networks. It uses weighted pair graphs and finite automata to determine them, and proves that the four notions are pairwise nonequivalent.

  • Problem

    Existing methods do not provide a unified determination of all four observability notions for Boolean control networks.

  • Method

    The paper constructs weighted pair graphs, transforms them into observability-specific deterministic finite automata, and applies automata theory to determine observability.

  • Results

    The approach determines all four observability types and shows that no pair of the four types is equivalent.

  • Takeaways & Limitations

    The results characterize the distinct observability notions of BCNs and expose their nonequivalence as an aspect of BCN nonlinearity.

Abstract

from arXiv · show

The problem on how to determine the observability of Boolean control networks (BCNs) has been open for five years already. In this paper, we propose a unified approach to determine all the four types of observability of BCNs in the literature. We define the concept of weighted pair graphs for BCNs. In the sense of each observability, we use the so-called weighted pair graph to transform a BCN to a finite automaton, and then we use the automaton to determine observability. In particular, the two types of observability that rely on initial states and inputs in the literature are determined. Finally, we show that no pairs of the four types of observability are equivalent, which reveals the essence of nonlinearity of BCNs.

I. INTRODUCTION

The paper addresses four distinct observability notions for BCNs and develops a unified finite-automata approach because existing methods do not cover them uniformly.

  • I. INTRODUCTION: Four observability notions are identified, including distinctions based on initial states, input sequences, and sufficiently long inputs.Existing work provides partial conditions or methods, while some observability problems are computationally hard.
  • I. INTRODUCTION: Because BCNs are polynomial systems over F2, observability notions involving initial states and inputs are important for these nonlinear systems.
  • I. INTRODUCTION: The proposed unified method constructs weighted pair graphs, transforms them into deterministic finite automata, and uses the automata to determine all four observability types.
  • I. INTRODUCTION: The paper organizes its development around algebraic preliminaries, observability algorithms, pairwise nonequivalence results, and concluding open problems.
  • I. INTRODUCTION: The preliminaries introduce semi-tensor products, logical matrices, Boolean-algebraic notation, and basic set and index conventions.

B. Boolean control networks and their algebraic forms

This section establishes Boolean-control-network and finite-automaton representations, then states the automata proposition used later to characterize observability.

  • B. Boolean control networks and their algebraic forms: A BCN has Boolean state, input, and output variables governed by logical functions f and h over the two-element field.
  • B. Boolean control networks and their algebraic forms: The semi-tensor product converts the BCN into an algebraic form with logical state, input, and output vectors and matrices L and H.
  • C. Formal languages and finite automata: A formal language is a set of finite words over an alphabet, with word length and concatenation providing the basic sequence notation.
  • C. Formal languages and finite automata: A deterministic finite automaton consists of states, an alphabet, a partial transition function, an initial state, and final states, and recognizes a regular language.
  • C. Formal languages and finite automata: The transition graph records automaton states as vertices and groups input letters producing the same transition as edge weights.
  • C. Formal languages and finite automata: The paper introduces a finite-automata proposition as the basis for its later observability tests.
  • C. Formal languages and finite automata: If every state is final and reachable, the recognized language equals the entire alphabet-star language exactly when the automaton is complete.

A. Weighted pair graph

The weighted pair graph represents BCN state pairs with identical outputs and their input-driven transitions, providing the graph structure used to build observability automata.

  • A. Weighted pair graph: Weighted pair graphs are the common intermediate representation from which observability-specific deterministic finite automata are constructed.
  • A. Weighted pair graph: Vertices are unordered state pairs producing the same output, and diagonal vertices contain identical states.
  • A. Weighted pair graph: An edge connects two pair-vertices when one input drives the two component states to the corresponding states of the destination pair, possibly with swapped order.
  • A. Weighted pair graph: Each edge weight contains the inputs that realize the associated pair transition.
  • A. Weighted pair graph: The section illustrates the construction with the weighted pair graph of BCN (3) and an input-state-output-time transfer graph for BCN (2).
  • A. Weighted pair graph: Testing BCN observability amounts to testing whether input sequences distinguish states that initially produce the same output.

B. Notations

The section defines finite and infinite input words and maps input sequences from an initial state to state and output trajectories over finite or infinite horizons.

  • B. Notations: The input, state, and output alphabets are denoted by ΔM, ΔN, and ΔQ, respectively.
  • B. Notations: For a finite input word and initial state, the BCN mappings produce finite state and output sequences.
  • B. Notations: For an infinite input sequence and initial state, the corresponding mappings produce infinite state and output sequences.
  • B. Notations: Subwords are indexed by positions, while U^∞ denotes the infinite concatenation of copies of a finite word.

C. Determining the observability in [6]

For observability based on initial states, the paper constructs a DFA from the weighted pair graph and characterizes non-observability through completeness. This provides a direct test illustrated on BCN (3).

  • C. Determining the observability in [6]: The construction uses the input alphabet as DFA symbols and propagates subsets of weighted-pair-graph vertices until no new states occur.All obtained DFA states are then made final.
  • C. Determining the observability in [6]: The DFA-based test is equivalent to checking whether one such DFA is complete.This follows from the construction and Proposition 2.1.
  • C. Determining the observability in [6]: A BCN is not observable iff a DFA associated with a non-diagonal weighted-pair-graph vertex recognizes all finite input sequences.The DFA accepts exactly sequences that do not determine the selected initial state.
  • C. Determining the observability in [6]: For BCN (3), the DFA associated with δ2 4 is complete, so the network is not observable under this definition.The example derives this DFA from Fig. 3 and applies Theorem 3.3.

D. Determining the observability in [7]

For observability based on initial states and inputs, the paper transforms weighted pair graphs into DFAs that track indistinguishable state pairs. Non-observability is characterized both by universal language recognition and by DFA completeness.

  • D. Determining the observability in [7]: Algorithm 3.5 uses input symbols as edge labels, starts from a non-diagonal state pair, retains reachable vertices, and marks the remainder as final states.The resulting DFA represents sequences that fail to distinguish the selected pair.
  • D. Determining the observability in [7]: A BCN is not observable iff a DFA generated from a non-diagonal weighted-pair-graph vertex recognizes (∆M)∗.The condition means every finite input sequence fails to distinguish the relevant state pair.
  • D. Determining the observability in [7]: Equivalently, non-observability holds iff at least one DFA generated by Algorithm 3.5 is complete.The theorem converts the language condition into a finite-automaton completeness test.
  • D. Determining the observability in [7]: For BCN (3), checking its three non-diagonal state pairs shows that the network is observable under this definition.The conclusion follows from the completeness checks described for the corresponding DFAs.
  • D. Determining the observability in [7]: The paper further gives an equivalent bounded-length condition using Nnd, the number of non-diagonal vertices in the weighted pair graph.For every distinct state pair, an input sequence of length Nnd must distinguish outputs whenever the initial outputs coincide.

E. Determining the observability in [8]

For observability requiring one input sequence to distinguish all state pairs, the paper constructs a DFA over subsets of non-diagonal weighted-pair-graph vertices. Non-observability is equivalent to this DFA being universal or complete.

  • E. Determining the observability in [8]: AVn begins with all non-diagonal weighted-pair-graph vertices and uses subsets of those vertices as DFA states.Transitions update the set of state pairs reachable under each input; an empty successor makes the partial transition undefined.
  • E. Determining the observability in [8]: A BCN is not observable iff the DFA AVn recognizes (∆M)∗.AVn accepts every finite input sequence that fails to distinguish all non-diagonal state pairs.
  • E. Determining the observability in [8]: Equivalently, non-observability holds iff AVn, generated by Algorithm 3.10, is complete.This gives a direct automaton-based decision criterion.
  • E. Determining the observability in [8]: For BCN (3), the DFA for its three non-diagonal state pairs is complete, so the network is not observable under this definition.The conclusion is drawn from Fig. 5 and Theorem 3.12.
  • E. Determining the observability in [8]: The paper notes that determining each of the four observability types is NP-hard.It contrasts the automaton method with enumerating all input sequences of a common finite length.

F. Determining the observability in [14]

For the observability notion in Definition 7, weighted pair graphs and finite-automaton cycles provide equivalent tests for determining whether a BCN is observable.

  • F. Determining the observability in [14]: The transition graph of the DFA generated from a non-diagonal weighted-pair-graph vertex has a cycle exactly when the BCN fails observability.The equivalence follows from finiteness of the transition graph and the existence of a repeating input sequence.
  • F. Determining the observability in [14]: A BCN is not observable exactly when a weighted pair graph contains a cycle involving a non-diagonal vertex or reachable from one.This criterion converts the observability question into a graph-structural test.
  • F. Determining the observability in [14]: An equivalent criterion checks all distinct periodic state-input trajectories having the same minimal period and length, with a critical length sufficient for the test.If no input sequence of that critical length determines the initial states, no other length can do so.
  • F. Determining the observability in [14]: The number of non-diagonal weighted-pair-graph vertices yields a finite test horizon for distinguishing every pair of distinct initial states under every input sequence.Theorem 3.17 uses Nnd as the maximum length needed in its finite criterion.

IV. PAIRWISE NONEQUIVALENCE OF THE FOUR TYPES OF OBSERVABILITY OF BOOLEAN CONTROL NETWORKS

The paper establishes that the four observability notions for Boolean control networks are pairwise nonequivalent, using counterexamples to separate them.

  • IV. PAIRWISE NONEQUIVALENCE OF THE FOUR TYPES OF OBSERVABILITY OF BOOLEAN CONTROL NETWORKS: The nonequivalence result covers all pairs of the four observability types and is presented as revealing the essence of BCN nonlinearity.The paper states this conclusion explicitly and illustrates it in Fig. 9.
  • IV. PAIRWISE NONEQUIVALENCE OF THE FOUR TYPES OF OBSERVABILITY OF BOOLEAN CONTROL NETWORKS: Observability in the sense of Definition 4 implies observability in the sense of Definition 5, but the converse fails.BCN (3) is used as a counterexample to the converse implication.
  • IV. PAIRWISE NONEQUIVALENCE OF THE FOUR TYPES OF OBSERVABILITY OF BOOLEAN CONTROL NETWORKS: The counterexample BCN (3) is not observable under Definition 4 because no input sequence can make its output determine the relevant initial state.The argument considers the relevant state and notes that all input sequences fail to identify it from the outputs.

4. Then for each such U, (HL)N

The paper uses weighted pair graphs and finite automata to analyze the four observability notions, proving implication relations and nonequivalence through BCN examples.

  • BCN (3) is observable under Definition 5 but not under Definition 7, demonstrating that the converse of the Definition 7 implication fails.
  • Theorems establish that observability in Definition 7 implies observability in Definitions 4, 5, and 6, while the converses fail.These results provide one-way implication relations among the observability notions.
  • The examples also distinguish Definition 6 from Definition 4, since BCN (6) is observable under Definition 6 while BCN (3) is not observable under Definition 4.
  • The weighted pair graph and its derived DFA encode state pairs and inputs, enabling automata-based tests of observability.
  • BCN (7) is observable under Definition 4 but not under Definition 7, providing a second counterexample to converse equivalence.

V. CONCLUDING REMARKS

The paper completes the determination of all four BCN observability types using finite automata and shows that no pair of types is equivalent. Its algorithms nevertheless have exponential or doubly exponential complexity.

  • Finite-automata techniques completely determine observability for Boolean control networks, and counterexamples show that no pair of the four notions is equivalent.
  • The first and fourth observability algorithms have exponential complexity, whereas the other two have doubly exponential complexity.
Loading 1405.6780v2…