PaperlayerView exact revision on arXiv

Source-linked AI summary

From 2D system to 1D system via restriction to a vertical strip: applications to time-controllability and zero-time-controllability

Aishwarya Bharti, Debasattam Pal

arXiv:2610.08415v1eess.SYcs.SY

TL;DR

The paper asks how finite vertical-strip restrictions of 2D systems can be represented as 1D systems. It gives a constructive proof and Gröbner basis algorithm, then applies them to controllability testing and trajectory generation. For scalar autonomous systems with either controllability property, the induced 1D system generates all admissible trajectories.

  • Problem

    The paper investigates whether the finite-interval restriction used in 1D system analysis has an analogous representation for 2D systems.

    Source: §I · p. 1

  • Method

    The paper constructively proves the vertical-strip restriction result and uses a Gröbner basis-based algorithm to compute the restricted 1D system.

    Source: §I · p. 1

  • Results

    The framework yields tests for time-controllability and zero-time-controllability of scalar autonomous 2D systems, and the induced 1D system generates all admissible trajectories when either property holds.

    Source: §I · p. 1, §VI · p. 6

  • Takeaways & Limitations

    For systems with either controllability property, trajectory generation can use the associated 1D system, reducing computational complexity.

    Source: §I · p. 1

Abstract

from arXiv · show

Motivated by the role of finite-time restriction in one-dimensional (1D) systems, we investigate the restriction of two-dimensional (2D) systems defined over $\mathbb{N}^2$ to a vertical strip. We give a constructive proof that such a restriction induces a 1D system. A Gr\"obner basis-based algorithm is then developed to compute this restricted 1D system from a given 2D system. The framework is then applied to develop an algorithm for testing the time-controllability and zero-time-controllability of scalar autonomous 2D systems; these properties are known to be equivalent to the existence of a deadbeat controller. Finally, we show that, for time-controllable or zero-time-controllable scalar autonomous 2D systems, the induced 1D system generates all the admissible trajectories of the original 2D system, thereby reducing the complexity of trajectory generation.

I. INTRODUCTION

The paper studies whether restricting a 2D system to a finite vertical strip yields a useful 1D system, motivated by finite-time analysis in 1D. It constructs that restricted system and applies it to controllability testing and trajectory generation.

I. INTRODUCTION

  • Finite-duration observations suffice to characterize and analyze 1D systems under suitable informativity conditions, motivating investigation of analogous results for 2D systems.The paper treats the first independent variable as time, while noting that 2D systems generally lack a fixed-direction notion of causality.Source: §I · p. 1
  • The paper develops a constructive proof and Gröbner basis-based algorithm to compute the 1D system governing trajectories restricted to a vertical strip.Earlier work established existence of a kernel representation for this restriction but did not provide a method to obtain it.Source: §I · p. 1
  • For scalar autonomous 2D systems, the framework yields tests for time-controllability and zero-time-controllability, with zero-time-controllability equivalent to existence of a deadbeat controller.The paper also states that the induced 1D system generates all admissible trajectories when either property holds, reducing trajectory-generation complexity.Source: §I · p. 1
  • The paper presents the constructive restriction result, its Gröbner basis algorithm, and the scalar autonomous controllability application in successive sections.The application tests time-controllability and zero-time-controllability.Source: §I · p. 1

II. PRELIMINARIES

The preliminaries define 2D systems as trajectories satisfying constant-coefficient partial difference equations and set up the vertical-strip restriction. A strip trajectory becomes a 1D trajectory indexed by the second coordinate.

II. PRELIMINARIES

  • A 2D system is a set of trajectories on N^2 satisfying constant-coefficient partial difference equations, expressed using forward shifts in the two coordinates.The equations have only finitely many nonzero coefficient matrices.Source: §II · p. 2
  • A behavior is represented as the kernel of a polynomial matrix, and its equation module is uniquely associated with that behavior.The kernel representation matrix itself need not be unique.Source: §II · p. 2
  • Restricting a trajectory to S0,H collects its H+1 values in the first coordinate into a vector indexed by the second coordinate, yielding a 1D trajectory.The strip consists of 0≤h≤H across k∈S.Source: §II · p. 2
  • The restricted behavior is known to admit a 1D kernel representation, while the paper's next section constructs that representation.The earlier result establishes existence only [9].Source: §II · p. 2

III. RESTRICTION OF B TO THE VERTICAL STRIP S0,H

The section constructs the kernel representation of a 2D behavior restricted to a vertical strip. It identifies the restricted behavior exactly as the kernel of a polynomial matrix in the second shift variable.

III. RESTRICTION OF B TO THE VERTICAL STRIP S0,H

  • The construction maps each equation of σt-degree at most H to a row of coefficients in σs, stacking its coefficients from powers 0 through H.This coefficient map ψ is bijective and As-linear.Source: §III · pp. 2–3
  • The restricted behavior BS0,H is a 1D behavior with kernel representation ker PH(σs).The rows of ψ⁻¹(PH(σs)) form an As-module basis for RH, the equation-module elements of σt-degree at most H.Source: §III · p. 3
  • Every full 2D trajectory restricts to a trajectory satisfying PH(σs)w|S0,H=0.The proof uses that the lifted rows belong to the equation module R, whose elements annihilate trajectories in B.Source: §III · p. 3
  • Conversely, every 1D trajectory in ker PH(σs) is the restriction of some trajectory in the original 2D behavior.The proof obtains this extension through the module representation and a commutative diagram.Source: §III · p. 3

IV. CONSTRUCTING A REPRESENTATION OF BS0,H USING GR ¨OBNER BASIS

The section develops a Gröbner-basis algorithm for computing a kernel representation of the behavior restricted to a vertical strip. Its restriction-revealing order addresses why simply selecting low-degree original generators can fail.

IV. CONSTRUCTING A REPRESENTATION OF BS0,H USING GR ¨OBNER BASIS

  • At H = 0, R_H can be nontrivial even when none of the original generators lies in it, because higher-degree terms may cancel.This is why selecting original generators by σ_t-degree alone does not generally produce generators for R_H.Source: §IV · p. 3
  • The restriction-revealing term order is term-over-position, with lexicographic monomials ordered by σ_t ≻ σ_s.The paper uses this order for the Gröbner basis that reveals the restriction-relevant generators.Source: §IV · p. 3
  • Lemma 4 constructs generators for R_H from the RR Gröbner basis using bounded σ_t-shifts of basis elements whose degrees fit within H.The resulting set G_H generates R_H as an A_s-module.Source: §IV · p. 4
  • The algorithm computes an RR Gröbner basis, forms G_H, and sets P(σ_s) = ψ(col{G_H}); the restricted behavior is ker P(σ_s).These are the stated computation steps for a 2D behavior and strip width H.Source: §IV · p. 4
  • Algorithm 1 outputs a kernel representation of the restricted 1D behavior B_S0,H.The proof uses Lemma 4 to generate R_H and Theorem 2 to construct P(σ_s).Source: §IV · p. 4

V. APPLICATION TO TIME-CONTROLLABILITY AND ZERO-TIME-CONTROLLABILITY

The section develops an algorithm to test time-controllability and zero-time-controllability in scalar autonomous 2D systems, using algebraic characterizations of these properties. It also connects the tests to trajectory generation by the corresponding 1D system.

V. APPLICATION TO TIME-CONTROLLABILITY AND ZERO-TIME-CONTROLLABILITY

  • Time-controllability requires patching on an initial vertical strip and a sufficiently distant half-plane, while zero-time-controllability patches an arbitrary trajectory with zero on these sets.The sets are S0,N−1 and SN+L→.Source: §V · p. 5
  • Every time-controllable behaviour is zero-time-controllable, but the converse does not hold.The section applies its characterization to scalar autonomous behaviours with a nonzero kernel representation matrix.Source: §V · pp. 4–5
  • For time-controllable or zero-time-controllable scalar autonomous systems, the corresponding 1D system generates every admissible trajectory of the 2D system.The paper identifies this substitution as a way to reduce trajectory-generation complexity.Source: §V · p. 5
  • The testing result uses that these systems’ equation ideals admit a single generator, although a 2D equation ideal need not be principal in general.The algorithm calculates a Gröbner basis and searches widths only up to an assumed upper bound Hmax.Source: §V · pp. 5–6
  • For time-controllability, Lemma 9 requires the H=0 restriction module to generate the equation ideal; zero-time-controllability requires a first qualifying width r with the stated shift condition.For zero-time-controllability, the restriction modules must be empty for H<r, and at H=r the generated ideal must equal R with σ_t^-r g in A_s for each g in G.Source: §V · p. 5
  • Algorithm 2 tests time-controllability and zero-time-controllability and returns δ(σs) when either property holds.It computes a Gröbner basis and searches strip widths up to the supplied Hmax; Theorem 10 establishes the test’s correctness.Source: §V · p. 6

VI. CONCLUSION

The paper constructs a proof and Gröbner basis-based algorithm for deriving the 1D system induced by restricting a 2D system to a vertical strip. For scalar autonomous 2D systems, it applies this framework to test controllability properties and compute a 1D system that determines the original system’s entire trajectory when those properties hold.

VI. CONCLUSION

  • For scalar autonomous 2D systems, the framework tests time-controllability and zero-time-controllability and, when either holds, computes a 1D system that determines the original system’s entire trajectory.Source: §VI · p. 6
  • A constructive proof establishes that restricting a 2D system to a vertical strip yields a 1D behaviour.Source: §VI · p. 6
  • The paper introduces restriction-revealing term ordering and a Gröbner basis-based algorithm to compute the restricted 1D system for a given 2D system.Source: §VI · p. 6
  • Future work will extend the proposed approach to general 2D systems.Source: §VI · p. 6
Loading 2610.08415v1…