Search

Weighted finite automata over the field of rational numbers and unary alphabets are considered. The notion of a characteristic polynomial is introduced for such automata as a means to provide a decidable necessary and sufficient condition, under which a unary weighted automaton admits a deterministic, i.e., sequential equivalent. The sequentiality problem for univariate rational series is thus proved to be decidable both over the rational numbers and over the integers, confirming a conjecture of S. Lombardy and J. Sakarovitch; its decidability over the nonnegative integers is observed as well. The decision algorithm proposed for these tasks is shown to run in polynomial time. A determinisation algorithm for determinisable unary weighted automata over the rational numbers is also described.

We revisit the single-machine preemptive scheduling problem to minimize total completion time with release times and deadlines. Du and Leung (1993) showed that the problem is binary NP-hard. But the exact complexity (unary NP-hardness or pseudo-polynomial-time solvability) of the problem is a long standing open problem. We show in this paper that the problem is unary NP-hard.

Let $T$ be a theory. If $T$ eliminates $\exists^\infty$, it need not follow that $T^{eq}$ eliminates $\exists^\infty$, as shown by the example of the $p$-adics. We give a criterion to determine whether $T^{eq}$ eliminates $\exists^\infty$. Specifically, we show that $T^{eq}$ eliminates $\exists^\infty$ if and only if $\exists^\infty$ is eliminated on all interpretable sets of "unary imaginaries." This criterion can be applied in cases where a full description of $T^{eq}$ is unknown. As an application, we show that $T^{eq}$ eliminates $\exists^\infty$ when $T$ is a C-minimal expansion of ACVF., Comment: 6 pages

We consider tensor grammars, which are an example of \commutative" grammars, based on the classical (rather than intuitionistic) linear logic. They can be seen as a surface representation of abstract categorial grammars ACG in the sense that derivations of ACG translate to derivations of tensor grammars and this translation is isomorphic on the level of string languages. The basic ingredient are tensor terms, which can be seen as encoding and generalizing proof-nets. Using tensor terms makes the syntax extremely simple and a direct geometric meaning becomes transparent. Then we address the problem of encoding noncommutative operations in our setting. This turns out possible after enriching the system with new unary operators. The resulting system allows representing both ACG and Lambek grammars as conservative fragments, while the formalism remains, as it seems to us, rather simple and intuitive., Some computational errors corrected. The final version of this draft was published in Jpurnal of Logic and Computation, Oxford University press

An interatomic potential for the ternary Ag–Cu–Sn system, an important material system related to the applications of lead-free solders, is developed on the basis of the second nearest-neighbor modified embedded-atom-method formalism. Potential parameters for the ternary and related binary systems are determined based on the recently improved unary description of pure Sn and the present improvements to the unary descriptions of pure Ag and Cu. To ensure the sufficient performance of atomistic simulations in various applications, the optimization of potential parameters is conducted based on the force-matching method that utilizes density functional theory predictions of energies and forces on various atomic configurations. We validate that the developed interatomic potential exhibits sufficient accuracy and transferability to various physical properties of pure metals, intermetallic compounds, solid solutions, and liquid solutions. The proposed interatomic potential can be straightforwardly used in future studies to investigate atomic-scale phenomena in soldering applications. Graphical abstract

Searching a condensed adequate set of k -valued logic is a challenging problem. Using algebraic expression of logical functions, a normal form for k -valued logic was presented in Cheng et al. [3]. Starting from the normal form, searching adequate set of k -valued logic is converted to searching set of generators of their isomorphic matrix group/semigroup. Two adequate sets of k -valued logic are revealed, which consist of only 4 logical operators: one binary and three unary operators. These two adequate sets are uniformly defined for all k ≥ 3 .

Predicting the life of Ni-Cd battery for electric multiple units (EMU) can not only improve the safety and reliability of battery, but also reduce the operating costs of EMU. For this reason, a life prediction method based on linear Wiener process is proposed, which is suitable for both monotonic and non-monotonic degraded systems with accurate results. Firstly, a unary linear Wiener degradation model is established, and the parameters of the model are estimated by using the expectation-maximization algorithm (EM). With the established model, the remaining useful life (RUL) of Ni-Cd battery and its distribution are obtained. Then based on the unary Wiener process degradation model, the correlation between capacity and energy is analyzed through Copula function to build a binary linear Wiener degradation model, where its parameters are estimated using Markov Chain Monte Carlo (MCMC) method. Finally, according to the binary Wiener process model, the battery RUL and its distribution are acquired. The experimental results show that the binary linear Wiener degradation model based on capacity and energy possesses higher accuracy than the unary linear wiener process degradation model.

Adversarial computations are a widely studied class of computations where resource-bounded probabilistic adversaries have access to oracles, i.e., probabilistic procedures with private state. These computations arise routinely in several domains, including security, privacy and machine learning. In this paper, we develop program logics for reasoning about adversarial computations in a higher-order setting. Our logics are built on top of a simply typed $\lambda$-calculus extended with a graded monad for probabilities and state. The grading is used to model and restrict the memory footprint and the cost (in terms of oracle calls) of computations. Under this view, an adversary is a higher-order expression that expects as arguments the code of its oracles. We develop unary program logics for reasoning about error probabilities and expected values, and a relational logic for reasoning about coupling-based properties. All logics feature rules for adversarial computations, and yield guarantees that are valid for all adversaries that satisfy a fixed resource policy. We prove the soundness of the logics in the category of quasi-Borel spaces, using a general notion of graded predicate liftings, and we use logical relations over graded predicate liftings to establish the soundness of proof rules for adversaries. We illustrate the working of our logics with simple but illustrative examples., Comment: Full version of ICFP 21 paper

We prove that the reachability problem for two-dimensional vector addition systems with states is NL-complete or PSPACE-complete, depending on whether the numbers in the input are encoded in unary or binary. As a key underlying technical result, we show that, if a configuration is reachable, then there exists a witnessing path whose sequence of transitions is contained in a bounded language defined by a regular expression of pseudo-polynomially bounded length. This, in turn, enables us to prove that the lengths of minimal reachability witnesses are pseudo-polynomially bounded.

Aiming at exploiting the discriminative deep features and encoding the high-level structures, this letter presents a deep-features-based high-order triple discriminative random field model, abbreviated as DF-HoTDF, for nonstationary polarimetric synthetic aperture radar (PolSAR) image classification. First, the DF-HoTDF model extracts the discriminative deep features by a graph-based complex-valued 3-D convolutional neural network (CV-3-D-CNN) and then constructs the unary potential by a negative log function. Second, it introduces an auxiliary field $u$ to explicitly regulate the nonstationary label patterns of the PolSAR image and then constructs a pairwise potential guided by $u$ to capture greater pairwise label interactions. Third, it defines a high-order potential on high-order cliques to encode high-level structures. Finally, under the discriminative model framework, the DF-HoTDF model has a weighted fusion of the unary potential, the pairwise potential, and the high-order potential. Then, with the DF-HoTDF model, we iteratively optimize the class label and the stationary maps until they converge. The experimental results demonstrate that the proposed DF-HoTDF model is of superior performances in nonstationary PolSAR image classification and that it can provide better label consistency in homogeneous region and better target structures and edge locations in heterogeneous region.

This paper answers several open questions around structures with o-minimal open core. We construct an expansion of an o-minimal structure $\mathcal{R}$ by a unary predicate such that its open core is a proper o-minimal expansion of $\mathcal{R}$. We give an example of a structure that has an o-minimal open core and the exchange property, yet defines a function whose graph is dense. Finally, we produce an example of a structure that has an o-minimal open core and definable Skolem functions, but is not o-minimal.

There are two types of stateless deterministic ordered restarting automata that both characterize the class of regular languages: the stl-det-ORWW-automaton and the stl-det-ORRWW-automaton. For the former a notion of reversibility has been introduced and studied that is very much tuned to the way in which restarting automata work. Here we suggest another, more classical, notion of reversibility for stl-det-ORRWW-automata, and we show that each regular language is accepted by such a reversible stl-det-ORRWW-automaton. We study the descriptional complexity of these automata, showing that they are exponentially more succinct than nondeterministic finite-state acceptors. We also look at the case of unary input alphabets.

We investigate finite automata whose state graphs are undirected. This means that for any transition from state p to q consuming some letter a from the input there exists a symmetric transition from state q to p consuming a letter a as well. So, the corresponding language families are subregular, and in particular in the deterministic case, subreversible. In detail, we study the operational descriptional complexity of deterministic and nondeterministic undirected finite automata. To this end, the different types of automata on alphabets with few letters are characterized. Then, the operational state complexity of the Boolean operations as well as the operations concatenation and iteration is investigated, where tight upper and lower bounds are derived for unary as well as arbitrary alphabets under the condition that the corresponding language classes are closed under the operation considered.

General matrix multiplication (GEMM) is pervasive in various domains, such as signal processing, computer vision, and machine learning. Conventional binary architectures for GEMM exhibit poor scalability in area and energy efficiency, due to the spatial nature of number representation and computing. On the contrary, unary computing processes data in temporal domain with extremely simple logic. However, to date, there rarely exist efficient architectures for unary GEMM. In this work, we first present uGEMM, a hardware-efficient unary GEMM architecture enabled by universally compatible arithmetic units, which simultaneously achieves input-insensitivity and high output accuracy. Next, we demonstrate that the proposed uGEMM can reliably early terminate the computation and offers dynamic energy-accuracy scaling for real-world applications via an accuracy-aware metric. Finally, to propel the future research for unary computing, we open source our unary computing simulator, UnarySim.

We introduce the notion of a Σω-bounded structure and specify a necessary and sufficient condition for a universal Σ-function to exist in a hereditarily finite superstructure over such a structure, for the class of all unary partial Σ-functions assuming values in the set ω of natural ordinals. Trees and equivalences are exemplified in hereditarily finite superstructures over which there exists no universal Σ-function for the class of all unary partial Σ-functions, but there exists a universal Σ-function for the class of all unary partial Σ-functions assuming values in the set ω of natural ordinals. We construct a tree T of height 5 such that the hereditarily finite superstructure ℍ(T) over T has no universal Σ-function for the class of all unary partial Σ-functions assuming values 0, 1 only.

A two-dimensional automaton has a read-only input head that moves in four directions on a finite array of cells labeled by symbols of the input alphabet. A three-way two-dimensional automaton is prohibited from making upward moves, while a two-way two-dimensional automaton can only move downward and rightward. We show that the language emptiness problem for unary three-way nondeterministic two-dimensional automata is NP -complete, and is in P for general-alphabet two-way nondeterministic two-dimensional automata. We also show that the language equivalence and inclusion problems for two-way deterministic two-dimensional automata are decidable, while the language universality, equivalence, and inclusion problems for two-way nondeterministic two-dimensional automata are undecidable. The deterministic case is the first known positive decidability result for a language equivalence problem on two-dimensional automata over a general alphabet. Finally, we discuss the notion of row and column projection languages. We show that the row projection language of a unary three-way nondeterministic two-dimensional automaton is always regular, and that there exists a unary three-way deterministic two-dimensional automaton with a nonregular column projection language. For two-way nondeterministic two-dimensional automata, on the other hand, both the row and column projection languages are always regular.

The first definition of space complexity for P systems was based on a hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A different approach can also be considered, having in mind an implementation of P systems in silico; in this case, the multiplicity of each object in each membrane can be stored using binary numbers, thus reducing the amount of needed space. In this paper, we give a formal definition for this alternative space complexity measure, we define the corresponding complexity classes and we compare such classes both with standard space complexity classes and with complexity classes defined in the framework of P systems considering the original definition of space.

In Gua, an underdocumented Tano Guang language spoken in Ghana, regressive ATR vowel harmony applies within words and non-iteratively across word boundaries. Although vowel harmony is known to cross word boundaries in some languages, little is known about the domains and extent of such harmony. We show that ATR harmony in Gua operates within phonological phrases that preferentially consist of two or three words, with binary phrases at the left edge and ternary phrases at the right edge of the utterance. Syntactic structure can exert an influence, but only with respect to subjects. In addition, we demonstrate that unary phrases are permitted, but not at the edge of the utterance. Gua is the first reported vowel harmony case that shows the same kind of phonological phrasing sensitivity as other prosodic phenomena, such as tone and duration.

Broadcast consensus protocols (BCPs) are a model of computation, in which anonymous, identical, finite-state agents compute by sending/receiving global broadcasts. BCPs are known to compute all number predicates in $\mathsf{NL}=\mathsf{NSPACE}(\log n)$ where $n$ is the number of agents. They can be considered an extension of the well-established model of population protocols. This paper investigates execution time characteristics of BCPs. We show that every predicate computable by population protocols is computable by a BCP with expected $\mathcal{O}(n \log n)$ interactions, which is asymptotically optimal. We further show that every log-space, randomized Turing machine can be simulated by a BCP with $\mathcal{O}(n \log n \cdot T)$ interactions in expectation, where $T$ is the expected runtime of the Turing machine. This allows us to characterise polynomial-time BCPs as computing exactly the number predicates in $\mathsf{ZPL}$, i.e. predicates decidable by log-space bounded randomised Turing machine with zero-error in expected polynomial time where the input is encoded as unary., Comment: To be published in the Proceedings of the 24th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), 2021

Unary functions definable in o-stable ordered groups of nonvaluational type are studied. Such functions are proved to be piecewise monotone and continuous.

Influence of component matching errors becomes more and more significant for integrated circuit design, in particular, for digital-to-analog converters. A unary digital-to-analog converter can compensate such errors by means of a switching scheme. This brief proposes a novel technique for a placement of element parts – the Multi-Flip Technique. This technique completely compensates a rotation of an error gradient when using as few as 16 parts for each element. An analytic proof and simulation results confirm its efficiency. Moreover, the technique is capable of being scaled while preserving the property of the rotation compensation.

The Closest Substring problem asks whether there exists a consensus string w of given length l such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has been studied for finite sets of strings and is known to be NP -hard. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFA) is PSPACE -complete. The problem remains PSPACE -hard even when the input is a deterministic finite automaton and the length l and radius r are given in unary. Also we show that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both NP -hard and coNP -hard.

The collection of multidimensional crowdsourced data has caused a public concern because of the privacy issues. To address it, local differential privacy (LDP) is proposed to protect the crowdsourced data without much loss of usage, which is popularly used in practice. However, the existing LDP protocols ignore users’ personal privacy requirements in spite of offering good utility for multidimensional crowdsourced data. In this paper, we consider the personality of data owners in protection and utilization of their multidimensional data by introducing the notion of personalized LDP (PLDP). Specifically, we design personalized multiple optimized unary encoding (PMOUE) to perturb data owners’ data, which satisfies ϵ total -PLDP. Then, the aggregation algorithm for frequency estimation on multidimensional data under PLDP is developed, which is described in two situations. Experiments are conducted on four real datasets, and the results show that the proposed aggregation algorithm yields high utility. Moreover, case studies with four real datasets demonstrate the efficiency and superiority of the proposed scheme.

We present new results on the computational limitations of affine automata (AfAs). First, we show that using the endmarker does not increase the computational power of AfAs. Second, we show that the computation of bounded-error rational-valued AfAs can be simulated in logarithmic space. Third, we identify some logspace unary languages that are not recognized by algebraic-valued AfAs. Fourth, we show that using arbitrary real-valued transition matrices and state vectors does not increase the computational power of AfAs in the unbounded-error model. When focusing only the rational values, we obtain the same result also for bounded error. As a consequence, we show that the class of bounded-error affine languages remains the same when the AfAs are restricted to use rational numbers only.

For a completely distributive De Morgan algebra L, we develop a general framework of L-fuzzy rough sets. Said precisely, we introduce a pair of L-fuzzy approximation operators, called upper and lower L-fuzzifying approximation operators derived from general L-fuzzifying neighborhood systems. It is shown that the proposed approximation operators are a common extension of the L-fuzzifying approximation operators derived from L-fuzzy relations (INS 2019) and the approximation operators derived from general neighborhood systems (KBS 2014). Furthermore, we investigate the unary, serial, reflexive, transitive and symmetric conditions in general L-fuzzifying neighborhood systems, and then study the associated approximation operators from both a constructive method and an axiomatic method. Particularly, for transitivity (resp., symmetry), we give two interpretations, one is an appropriate generalization of transitivity (resp., symmetry) for L-fuzzy relations, and the other is a suitable extension of transitivity (resp., symmetry) for general neighborhood systems. In addition, for some special L-fuzzifying approximation operators, we use single axiom to characterize them, respectively. At last, the proposed approximation operators are applied in the research of incomplete information system, and a three-way decision model based on them is established. To exhibit the effectiveness of the model, a practical example is presented.

In the asphalt pavement structure design method, the structural analysis and design are generally performed in the form of point values. However, determining the point value form of design parameters based on the statistical analysis theory cannot fully reflect the complex properties such as variability and uncertainty of parameters. In order to further improve the reliability and practicability of pavement design parameters, in this article, we have introduced the interval number representation that can better reflect the complex nature of parameters; but the interval number algorithm is too complicated and common calculation tools and software are difficult to adopt, which limit the wide application of interval analysis to some extent. The article analyzes the algorithm of interval numbers, focusing on the analysis of interval numbers of unary and binary functions. In this way, the point number operation can be used to obtain the interval number result of the function consistent with the interval number algorithm, which avoids the complicated interval number operation process and the interval expansion. The point numerical function algorithm of interval numbers is verified by design parameters and the calculation of asphalt pavement structure such as axle load conversion, cumulative equivalent axis calculation, calculation of foundation layer tensile stress of each structure layer, calculation of mixture penetration strength, fatigue cracking check of asphalt mixture layer, permanent deformation check, and vertical pressure strain test of roadbed top surface. In conclusion, this research provides a simple and easy way to implement the application of mathematical tools for interval analysis, which is suitable for direct use for existing point numerical calculation tools and software.

In that paper we study atoms of congruence lattices and subdirectly irreducibility of algebras with one operator and the main symmetric operation. A ternary operation 𝑑(𝑥, 𝑦, 𝑧) satisfying identities 𝑑(𝑥, 𝑦, 𝑦) = 𝑑(𝑦, 𝑦, 𝑥) = 𝑑(𝑦, 𝑥, 𝑦) = 𝑥 is called a minority operation. The symmetric operation is a minority operation defined by specific way. An algebra 𝐴 is called subdirectly irreducible if 𝐴 has the smallest nonzero congruence. An algebra with operators is an universal algebra whose signature consists of two nonempty non-intersectional parts: the main one which can contain arbitrary operations, and the additional one consisting of operators. The operators are unary operations that act as endomorphisms with respect to the main operations, i.e., one that permutable with main operations. A lattice 𝐿 with zero is called atomic if any element of 𝐿 contains some atom. A lattice 𝐿 with zero is called atomistic if any nonzero element of 𝐿 is a join of some atom set. It shown that congruence lattices of algebras with one operator and main symmetric operation are atomic. The structure of atoms in the congruence lattices of algebras in given class is described. The full describe of subdirectly irreducible algebras and of algebras with an atomistic congruence lattice in given class is obtained.

The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.

In this paper, based on the existing research results, we obtain the unary extension 3-Lie algebras by one-dimensional extension of the known Lie algebra L. For two known 3-Lie algebras H, M, the (μ, ρ, β)-extension of H through M is given, and the necessary and sufficient conditions for the (μ, ρ, β)-extension algebra of H through M being 3-Lie algebra are obtained, and the structural characteristics and properties of these two kinds of extended 3-Lie algebras are given.

In this paper, we introduce a Sheffer stroke Hilbert algebra by giving definitions of Sheffer stroke and a Hilbert algebra. After it is shown that the axioms of Sheffer stroke Hilbert algebra are independent, it is given some properties of this algebraic structure. Then it is stated the relationship between Sheffer stroke Hilbert algebra and Hilbert algebra by defining a unary operation on Sheffer stroke Hilbert algebra. Also, it is presented deductive system and ideal of this algebraic structure. It is defined an ideal generated by a subset of a Sheffer stroke Hilbert algebra, and it is constructed a new ideal of this algebra by adding an element of this algebra to its ideal., Ege University Scientific Research Projects DirectorateEge University [20772], The authors would like to express their sincere thanks to the referee for their valuable suggestions and comments. This study is partially funded by Ege University Scientific Research Projects Directorate with the Project Number 20772.

We construct a formula $\phi$ which axiomatizes non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set $A \subseteq \mathbb{N}$ is a spectrum of a formula which has only planar models if numbers $n \in A$ can be recognized by a non-deterministic Turing machine (or a one-dimensional cellular automaton) in time $t(n)$ and space $s(n)$, where $t(n)s(n) \leq n$ and $t(n),s(n) = \Omega(\log(n))$., Comment: 9 pages, 1 figure

In this paper we survey our recent results characterizing various graph neural network (GNN) architectures in terms of their ability to classify nodes over graphs, for classifiers based on unary logical formulas- or queries. We focus on the language FOC2, a well-studied fragment of FO. This choice is motivated by the fact that FOC2 is related to theWeisfeiler-Lehman (WL) test for checking graph isomorphism, which has the same ability as GNNs for distinguishing nodes on graphs. We unveil the exact relationship between FOC2 and GNNs in terms of node classification. To tackle this problem, we start by studying a popular basic class of GNNs, which we call AC-GNNs, in which the features of each node in a graph are updated, in successive layers, according only to the features of its neighbors. We prove that the unary FOC2 formulas that can be captured by an AC-GNN are exactly those that can be expressed in its guarded fragment, which in turn corresponds to graded modal logic. This result implies in particular that ACGNNs are too weak to capture all FOC2 formulas. We then seek for what needs to be added to AC-GNNs for capturing all FOC2. We show that it suffices to add readouts layers, which allow updating the node features not only in terms of its neighbors, but also in terms of a global attribute vector. We call GNNs with readouts ACR-GNNs. We also describe experiments that validate our findings by showing that, on synthetic data conforming to FOC2 but not to graded modal logic, AC-GNNs struggle to fit in while ACR-GNNs can generalise even to graphs of sizes not seen during training.