Recognizing splicing languages: Syntactic monoids and simultaneous pumping

We use syntactic monoid methods, together with an enhanced pumping lemma, to investigate the structure of splicing languages. We obtain an algorithm for deciding whether a regular language is a reflexive splicing language, but the general question remains open.     

Hamiltonian cycles in planar triangulations with no separating triangles

A classical theorem of Hassler Whitney asserts that any maximal planar graph with no separating triangles is Hamiltonian. In this paper, we examine the problem of generalizing Whitney's theorem by relaxing the requirement that the triangulation be a maximal planar graph (i.e., that its outer boundary be a triangle) while maintaining the hypothesis that the triangulation have no separating triangles. It is shown that the conclusion of Whitney's theorem still holds if the chords satisfy a certain sparse-ness condition and that a Hamiltonian cycle through a graph satisfying this condition can be found in linear time. Upper bounds on the shortness coefficient of triangulations without separating triangles are established. Several examples are given to show that the theorems presented here cannot be extended without strong additional hypotheses. In particular, a 1-tough, non-Hamiltonian triangulation with no separating triangles is presented.     

ON SINGLE LAWS FOR VARIETIES OF QUASIGROUPS ASSOCIATED WITH EXTENDED CYCLE SYSTEMS

It has been previously shown by Lindner and Rodger that quasigroups associated with 2-perfect extended m-cycle systems can be equationally defined if and only if m ∈ {3, 5, 7}. In this paper we present a single identity for each such m which is equivalent to the identities given for these varieties.

     

Randomly matchable graphs

A graph is defined to be randomly matchable if every matching of G can be extended to a perfect matching. It is shown that the connected randomly matchable graphs are precisely K_2n and K_n,n (n ≥ 1).     

Re-Gauging Groupoid,Symmetries and Degeneracies for Graph Hamiltonians and Applications to the Gyroid Wire Network

We study a class of graph Hamiltonians given by a type of quiver representation to which we can associate (non)-commutative geometries. By selecting gauging data, these geometries are realized by matrices through an explicit construction or a Kan extension. We describe the changes in gauge via the action of a re-gauging groupoid. It acts via matrices that give rise to a noncommutative 2-cocycle and hence to a groupoid extension (gerbe). We furthermore show that automorphisms of the underlying graph of the quiver can be lifted to extended symmetry groups of re-gaugings. In the commutative case, we deduce that the extended symmetries act via a projective representation. This yields isotypical decompositions and super-selection rules. We apply these results to the primitive cubic, diamond, gyroid and honeycomb wire networks using representation theory for projective groups and show that all the degeneracies in the spectra are consequences of these enhanced symmetries. This includes the Dirac points of the G(yroid) and the honeycomb systems.     

Linearly Derived Steiner Triple Systems

We attach a graph to every Steiner triple system. The chromatic number of this graph is related to the possibility of extending the triple system to a quadruple system. For example, the triple systems with chromatic number one are precisely the classical systems of points and lines of a projective geometry over the two-element field, the Hall triple systems have chromatic number three (and, as is well-known, are extendable) and all Steiner triple systems whose graph has chromatic number two are extendable. We also give a configurational characterization of the Hall triple systems in terms of mitres.     

Codes and Anticodes in the Grassman Graph

Perfect codes and optimal anticodes in the Grassman graph G_q(n, k) are examined. It is shown that the vertices of the Grassman graph cannot be partitioned into optimal anticodes, with a possible exception when n=2k. We further examine properties of diameter perfect codes in the graph. These codes are known to be similar to Steiner systems. We discuss the connection between these systems and “real” Steiner systems.     

Categorical Approach to Horizontal Structuring and Refinement of High-Level Replacement Systems

Based on the well-known theory of high-level replacement systems – a categorical formulation of graph grammars – we present new results concerning refinement of high-level replacement systems. Motivated by Petri nets, where refinement is often given by morphisms, we give a categorical notion of refinement. This concept is called Q-transformations and is established within the framework of high-level replacement systems. The main idea is to supply rules with an additional morphism, which belongs to a specific class Q of morphisms. This leads to the new notions of Q-rules and Q-transformations. Moreover, several concepts and results of high-level replacement systems are extended to Q-transformations. These are sequential and parallel transformations, union, and fusion, based on different colimit constructions. The main results concern the compatibility of these constructions with Q-transformations that is the corresponding theorems for usual transformations are extended to Q-transformations. Finally, we demonstrate the application of these techniques for the special case of Petri nets to a case study concerning the requirements engineering of a medical information system.     

Synchronization of quaternion-valued coupled systems with time-varying coupling via event-triggered impulsive control

In this paper, the problem of exponential synchronization of quaternion-valued coupled systems based on event-triggered impulsive control is investigated for the first time. It should be pointed out that the coupling strength is quaternion-valued and time-varying, which makes our model more in line with practical models. First, we prove that event-triggered impulsive control can exclude Zeno behavior. Then, based on the Lyapunov method and the graph theory, some sufficient conditions are derived to ensure that quaternion-valued coupled systems reach synchronization. Furthermore, as an application of our theoretical results, exponential synchronization of quaternion-valued Kuramoto oscillators is studied in detail and a synchronization criterion is presented. Finally, some numerical simulations are given to show the effectiveness of our theoretical results.     

Double-Pullback Transitions and Coalgebraic Loose Semantics for Graph Transformation Systems

The classical algebraic approach to graph transformation is a mathematical theory based on categorical techniques with several interesting applications in computer science. In this paper, a new semantics of graph transformation systems (in the algebraic, double-pushout (DPO) approach) is proposed in order to make them suitable for the specification of concurrent and reactive systems. Classically, a graph transformation system comes with a fixed behavioral interpretation. Firstly, all transformation steps are intended to be completely specified by the rules of the system, that is, there is an implicit frame condition: it is assumed that there is a complete control about the evolution of the system. Hence, the interaction between the system and its (possibly unknown) environment, which is essential in a reactive system, cannot be modeled explicitly. Secondly, each sequence of transformation steps represents a legal computation of the system, and this makes it difficult to model systems with control. The first issue is addressed by providing graph transformation rules with a loose semantics, allowing for unspecified effects which are interpreted as activities of the environment. This is formalized by the notion of double-pullback transitions, which replace (and generalize) the well-known double-pushout diagrams by allowing for spontaneous changes in the context of a rule application. Two characterizations of double-pullback transitions are provided: the first one describes them in terms of extended direct DPO derivations, and the second one as incomplete views of parallel or amalgamated derivations. The issue of constraining the behavior of a system to transformation sequences satisfying certain properties is addressed instead by introducing a general notion of logic of behavioral constraints, which includes instances like start graphs, application and consistency conditions, and temporal logic constraints. The loose semantics of a system with restricted behavior is defined as a category of coalgebras over a suitable functor. Such category has a final object which includes all finite and infinite transition sequences satisfying the constraints.     

Connections among several chaos feedback control approaches and chaotic vibration control of mechanical systems

This study reveals the essential connections among several popular chaos feedback control approaches, such as delayed feedback control (DFC), stability transformation method (STM), adaptive adjustment method (AAM), parameter adjustment method, relaxed Newton method, and speed feedback control method (SFCM), etc. Meanwhile, the generality and practical applicability of these approaches are evaluated and compared. It is shown that for discrete chaotic maps, STM can be regarded as a kind of predictive feedback control, and AAM is actually a special case of STM which is merely effective for a particular dynamical system. The parameter adjustment method is only a different expression of the relaxed Newton method, and both of them represent just one search direction of STM, i.e., the gradient direction. Moreover, the intrinsic relation between the STM and SFCM for controlling the equilibrium of continuous autonomous systems is investigated, indicating that STM can be viewed as a special form of the SFCM. Finally, both the STM and SFCM are extended to control the chaotic vibrations of non-autonomous mechanical systems effectively.     

Post's closed systems and the weak chromatic number of hypergraphs

In the Post lattice of the families of closed systems (i.e. sets of boolean functions closed with respect to composition) the particular systems of monotonic functions are closely related to the classification of hypergraphs by their weak chromatic numbers. It is shown also that for k>3, the k-chromatic hypergraphs can be built from the complete graph K.     

Menus of kuratowski subgraphs

Motivated by heuristic embedding algorithms, this paper is concerned with the organization of potentially large lists of Kuratowski subgraphs of an arbitrary nonpianar graph. A graphical structure called a "nearly Hamiltonian" graph is defined. It is shown that lists of Kuralowski subgraphs can be lexicographically organized in such structures. It is shown that any nonpianar graph contains such structures and at least one such structure with a nonempty list of Kuratowski subgraphs can be located in linear time in ihe edges of the graph.     

Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: Stability and moving-horizon approximations

Stability results are given for a class of feedback systems arising from the regulation of time-varying discrete-time systems using optimal infinite-horizon and moving-horizon feedback laws. The class is characterized by joint constraints on the state and the control, a general nonlinear cost function and nonlinear equations of motion possessing two special properties. It is shown that weak conditions on the cost function and the constraints are sufficient to guarantee uniform asymptotic stability of both the optimal infinite-horizon and moving-horizon feedback systems. The infinite-horizon cost associated with the moving-horizon feedback law approaches the optimal infinite-horizon cost as the moving horizon is extended.     

Preordering saddle‐point systems for sparse LDLT factorization without pivoting

This paper focuses on efficiently solving large sparse symmetric indefinite systems of linear equations in saddle‐point form using a fill‐reducing ordering technique with a direct solver. Row and column permutations partition the saddle‐point matrix into a block structure constituting a priori pivots of order 1 and 2. The partitioned matrix is compressed by treating each nonzero block as a single entry, and a fill‐reducing ordering is applied to the corresponding compressed graph. It is shown that, provided the saddle‐point matrix satisfies certain criteria, a block LDL^T factorization can be computed using the resulting pivot sequence without modification. Numerical results for a range of problems from practical applications using a modern sparse direct solver are presented to illustrate the effectiveness of the approach.     

On the robustness of linear stabilizing feedback control for linear uncertain systems: Multi-input case

The robust stabilization of linear systems with constant uncertainties against structured perturbations using Lyapunov's theory is investigated. The only information needed on the uncertainties is the knowledge of their boundaries. The matching conditions of the uncertain systems are not required to be satisfied. It is first shown that, under some assumptions, the system can be transformed into a certain canonical controllable companion form. Then, under some additional assumptions, the existence of a linear controller which stabilizes the system based on Lyapunov's theory is shown.     

Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

It is shown that two sorts of problems belong to the NP-complete class. First, it is proven that for a given κ-colorable graph and a given κ-coloring of that graph, determining whether the graph is or is not uniquely κ-colorable is NP-complete. Second, a result by Garey, Johnson, and Stockmeyer is extended with a proof that the coloring of four-regular planar graphs is NP-complete.     

On stability of linear and weakly nonlinear switched systems with time delay

This paper studies time-delayed switched systems that include both stable and unstable modes. By using multiple Lyapunov-functions technique and a dwell-time approach, several criteria on exponential stability for both linear and nonlinear systems are established. It is shown that by suitably controlling the switching between the stable and unstable modes, exponential stabilization of the switched system can be achieved. Some examples and numerical simulations are provided to illustrate our results.