Narrow Results

A theory of representation of semiautomata by canonical words and equivalences was developed in [7]. That work was motivated by trace-assertion specifications of software modules, but its focus was entirely on the underlying mathematical model. In the present paper we extend that theory to automata with Moore and Mealy outputs, and show how to apply the extended theory to the specification of modules. In particular, we present a unified view of the trace-assertion methodology, as guided by our theory. We illustrate this approach, and some specific issues, using several nontrivial examples. We include a discussion of finite versus infinite modules, methods of error handling, some awkward features of the trace-assertion method, and a comparison to specifications by automata. While specifications by trace assertions and automata are equivalent in power, there are cases where one approach appears to be more natural than the other. We conclude that, for certain types of system modules, formal specification by automata, as opposed to informal state machines, is not only possible, but practical.

We consider the equivalence problem for labeled Markov chains (LMCs), where each state is labeled with an observation. Two LMCs are equivalent if every finite sequence of observations has the same probability of occurrence in the two LMCs. We show that equivalence can be decided in polynomial time, using a reduction to the equivalence problem for probabilistic automata, which is known to be solvable in polynomial time. We provide an alternative algorithm to solve the equivalence problem, which is based on a new definition of bisimulation for probabilistic automata. We also extend the technique to decide the equivalence of weighted probabilistic automata.

Then, we consider the equivalence problem for labeled Markov decision processes (LMDPs), which asks given two LMDPs whether for every scheduler (i.e. way of resolving the nondeterministic decisions) for each of the processes, there exists a scheduler for the other process such that the resulting LMCs are equivalent. The decidability of this problem remains open. We show that the schedulers can be restricted to be observation-based, but may require infinite memory.

Simulations of weighted tree automata (wta) are considered. It is shown how such simulations can be decomposed into simpler functional and dual functional simulations also called forward and backward simulations. In addition, it is shown in several cases (fields, commutative rings, NOETHERIAN semirings, semiring of natural numbers) that all equivalent wta M and N can be joined by a finite chain of simulations. More precisely, in all mentioned cases there is a single wta that simulates both M and N. Those results immediately yield decidability of equivalence provided that the semiring is finitely (and effectively) presented.

The decidability of equivalence for three important classes of tree transducers is discussed. Each class can be obtained as a natural restriction of deterministic macro tree transducers (MTTs): (1) no context parameters, i.e., top-down tree transducers, (2) linear size increase, i.e., MSO definable tree transducers, and (3) monadic input and output ranked alphabets. For the full class of mtts, decidability of equivalence remains a long-standing open problem.

We consider one of the weakest variants of cost register automata over a tropical semiring, namely copyless cost register automata over $\mathbb{N}$ with updates using $min$ and increments. We show that this model can simulate, in some sense, the runs of counter machines with zero-tests. We deduce that a number of problems pertaining to that model are undecidable, namely equivalence, upperboundedness, and semilinearity. In particular, the undecidability of equivalence disproves a conjecture of Alur et al. from 2012. To emphasize how weak these machines are, we also show that they can be expressed as a restricted form of linearly-ambiguous weighted automata.

A language over an alphabet $\mathsf{B}=\mathsf{A}\cup \overline{\mathsf{A}}$ of opening ($\mathsf{A}$) and closing ($\overline{\mathsf{A}}$) brackets, is balanced if it is a subset of the Dyck language ${𝔻}_{\mathsf{B}}$ over $\mathsf{B}$, and it is well-formed if all words are prefixes of words in ${𝔻}_{\mathsf{B}}$. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-$\mathsf{TW}$ of non-linear tree transducers with output alphabet $\mathsf{B}$ whether or not the output language is balanced.

We show that the equivalence, unambiguity, and sequentiality problems are decidable for finitely ambiguous max-plus tree automata. A max-plus tree automaton is a weighted tree automaton over the max-plus semiring. A max-plus tree automaton is called finitely ambiguous if the number of accepting runs on every tree is bounded by a global constant and it is called unambiguous if there exists at most one accepting run on every tree. For the equivalence problem, we show that for two finitely ambiguous max-plus tree automata, it is decidable whether both assign the same weight to every tree. For the unambiguity and sequentiality problems, we show that for every finitely ambiguous max-plus tree automaton, both the existence of an equivalent unambiguous automaton and the existence of an equivalent deterministic automaton are decidable.

Some special sets of ω-words, namely, the sets that can be obtained by catenating nonempty finite sets of words, an infinite number of times, are considered. A condition for the equality of two such sets of ω-words is obtained.

By applying the concept of geometric KdV flows into Kähler and para-Kähler manifolds, we give a unified geometric interpretation for the four typical integrable equations in the third-order system of the AKNS hierarchy. That is: the KdV equation, the mKdV equation, the complex mKdV^- equation and the complex mKdV⁺ equation are, respectively, equivalent to the first kind reduction, the second kind reduction of the geometric KdV flow of maps from R¹ to the de Sitter two-space S^1,1 ↪ R^2,1 (regarded as a para-Kähler manifold), the geometric KdV flow of maps from R¹ to the hyperbolic two-space H² ↪ R^2,1 (regarded as a Kähler manifold of noncompact type) and the geometric KdV flow of maps from R¹ to the two-sphere S² ↪ R³ (regarded as a Kähler manifold of compact type). This is an application of the general geometric KdV flows.

Contrary to complex structures, a generic almost complex structure J has no local symmetries. We give a criterion for finite-dimensionality of the pseudogroup G of local symmetries for a given almost complex structure J. It will be indicated that a large symmetry pseudogroup (infinite-dimensional) is a signature of some integrable structure, like a pseudoholomorphic foliation. We classify the sub-maximal (from the viewpoint of the size of G) symmetric structures J. Almost complex structures in dimensions 4 and 6 are discussed in greater details in this paper.

In this paper, a general relativistic wave equation is written to deal with electromagnetic waves in the background of the Shuwer. We obtain the exact form of this equation in a second-order form. On the other hand, by using spinor form of the Maxwell equations the propagation problem is reduced to the solution of the second-order differential equation of complex combination of the electric and magnetic fields. For these two different approaches, we obtain the spinors in terms of field strength tensor. We show that the Maxwell equations are equivalence to the mDKP equation in the Shuwer.

The analysis of the equivalence between the Hamiltonian and Lagrangian formalisms, for a sp(2) BRST theory, is achieved. The proof of this equivalence, apart from its intrinsic importance, allows the explanation of some results which seem artificially implanted in the theory: the structure of the extended spaces, and the form of the master equation. As a new image on the BRST operator, this paper suggests that its action can be split into a canonical part and a noncanonical part.

The Euclidean space, obtained by the analytical continuation of time, to an imaginary time, is used to model thermal systems. In this work, it is taken a step further to systems with spatial thermal variation, by developing an equivalence between the spatial variation of temperature in a thermal bath and the curvature of the Euclidean space. The variation in temperature is recast as a variation in the metric, leading to a curved Euclidean space. The equivalence is substantiated by analyzing the Polyakov loop, the partition function and the periodicity of the correlation function. The bulk thermodynamic properties like the energy, entropy and the Helmholtz free energy are calculated from the partition function, for small metric perturbations, for a neutral scalar field. The Dirac equation for an external Dirac spinor, traversing a thermal bath with spatial thermal gradients, is solved in the curved Euclidean space. The fundamental behavior exhibited by the Dirac spinor eigenstate, may provide a possible mechanism to validate the theory, at a more basal level, than examining only bulk thermodynamic properties. Furthermore, in order to verify the equivalence at the level of classical mechanics, the geodesic equation is analyzed in a classical backdrop. The mathematical apparatus is borrowed from the physics of quantum theory in a gravity-induced space–time curvature. As spatial thermal variations are obtainable at quantum chromodynamic or quantum electrodynamic energies, it may be feasible for the proposed formulation to be validated experimentally.

We construct the inverse partition semigroup, isomorphic to the dual symmetric inverse monoid, introduced in [6]. We give a convenient geometric illustration for elements of . We describe all maximal subsemigroups of and find a generating set for when X is finite. We prove that all the automorphisms of are inner. We show how to embed the symmetric inverse semigroup into the inverse partition one. For finite sets X, we establish that, up to equivalence, there is a unique faithful effective transitive representation of , namely to . Finally, we construct an interesting -cross-section of , which is reminiscent of , the -cross-section of , constructed in [4].

The complexity of the equation solvability problem is known for nilpotent groups, for not solvable groups and for some semidirect products of Abelian groups. We provide a new polynomial time algorithm for deciding the equation solvability problem over certain semidirect products, where the first factor is not necessarily Abelian. Our main idea is to represent such groups as matrix groups, and reduce the original problem to equation solvability over the underlying field. Further, we apply this new method to give a much more efficient algorithm for equation solvability over nilpotent rings than previously existed.

We provide a polynomial time algorithm for deciding the equation solvability problem over finite groups that are semidirect products of a $p$-group and an Abelian group. As a consequence, we obtain a polynomial time algorithm for deciding the equivalence problem over semidirect products of a finite nilpotent group and a finite Abelian group. The key ingredient of the proof is to represent group expressions using a special polycyclic presentation of these finite solvable groups.

A chord graph in $3$-space is constructed from a ribbon surface-link in $4$-space. In earlier papers, the three moves on the diagrams of chord graphs (namely, the chord diagrams) were introduced to describe the faithful equivalence of a ribbon surface-link. In this paper, it is shown that any two equivalent ribbon surface-links are faithfully equivalent, so that any chord diagrams of any two equivalent ribbon surface-links are connected by a finite number of these three moves. By combining it with an earlier result, it is shown that any two TOP-equivalent ribbon surface-links are equivalent. In other words, there is no exotic ribbon surface-link, generalizing an earlier result on the trivial ribbon surface-knot. In another earlier result, the three moves on the chord diagrams were modified into the 16 moves on the chord diagrams without base crossing. In this paper, further modified moves of the 16 moves on the chord diagrams without base crossing are also introduced to describe how the set of ribbon torus-links is produced from the set of welded virtual links.

Whether Jordan’s and Einstein’s frame descriptions of $F(R)$ theory of gravity are physically equivalent, is a long standing debate. However, practically none questioned on true mathematical equivalence, since classical field equations may be translated from one frame to the other following a transformation relation. Here, we show that, neither Noether symmetries, Noether equations, nor may quantum equations be translated from one to the other. The reason being, — conformal transformation results in a completely different system, with a different Lagrangian. Field equations match only due to the presence of diffeomorphic invariance. Unless a symmetry generator is found which involves Hamiltonian constraint equation, mathematical equivalence between the two frames appears to be vulnerable. In any case, in quantum domain, mathematical and therefore physical equivalence cannot be established.

Classical equivalence between Jordan’s and Einstein’s frame counterparts of $F(R)$ theory of gravity has recently been questioned, since the two produce different Noether symmetries, which could not be translated back and forth using transformation relations. Here we add the Hamiltonian constraint equation, which is essentially the time–time component of Einstein’s equation, through a Lagrange multiplier to the existence condition for Noether symmetry and show that all the three different canonical structures of $F(R)$ theory of gravity, including the one which follows from Lagrange multiplier technique, admit each and every available symmetry independently. This establishes classical equivalence.

We study the equivalence problem of submanifolds with respect to a transitive pseudogroup action. The corresponding differential invariants are determined via formal theory and lead to the notions of l-variants and l-covariants, even in the case of non-integrable pseudogroup. Their calculation is based on the cohomological machinery: we introduce a complex for covariants, define their cohomology and prove the finiteness theorem. This implies the well-known Lie–Tresse theorem about differential invariants. We also generalize this theorem to the case of pseudogroup action on differential equations.