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.

The design and principle of operation of a multi-sensor converter of binary mechanical signals into electrical signals based on a partitioned fiber-optic digital-to-analog converter with parallel structure are considered. The digital-to-analog converter is made from a set of simple and fiber-optic digital-to-analog sections adaptable to streamlined production (three- and five-bit). The advantages of the optical layout of the proposed converter on metrological and energy characteristics, in comparison with unary multi-bit converters, are substantiated. It is shown that as a result of an increase in the number of digital-to-analog sections, it is possible to increase by a large factor the information capacity of the multi-sensor converter without tightening the requirements for its manufacturing design and component base. A mathematical model of the proposed converter has been developed that reflects the features of functioning under conditions of time-sequenced conversion of the input mechanical code vectors of the separate fiber-optic sections into electrical analogs, and generating a resultant output code vector. The developed mathematical model can be used at the design phase for converters of binary mechanical signals, in order to obtain extensive and deep information on the engineering prospects of the future product, without resorting to expensive physical experiment.

We examine the accepting state complexity, i.e., the minimal number of accepting states of deterministic finite automata for languages resulting from unary and binary operations on languages with accepting state complexity given as a parameter. This is a continuation of the work of [J. Dassow: On the number of accepting states of finite automata, J. Autom., Lang. Comb., 21, 2016]. We solve most of the open problems mentioned thereof. In particular, we consider the operations of intersection, symmetric difference, right and left quotients, reversal, and permutation (on finite languages), where we obtain precise ranges of accepting state complexities. We also consider symmetric difference on unary finite languages where we obtain a non-contiguous range of accepting state complexities.

The paper describes equivalent conditions under which an arbitrary unary algebra has no proper subalgebras. An algorithm for checking the absence of subalgebras or for finding proper subalgebras and their generators in a given unary algebra whose carrier and signature are finite is proposed.

This brief proposes a new switching scheme without division of weighting elements into several parts for unary digital-to-analog converters. The switching scheme is universal, i.e., it can be applied to a unary array with an even resolution of 4 bits and higher. A comparison of universal switching schemes showed that the proposed switching scheme reduces the maximum integral nonlinearity by 12–44% relative to the best-known one, the $\text{Q}^{N}$ Rotated Walk. Moreover, the proposed switching scheme gives an improvement of up to 50% in a comparison with non-universal switching schemes.

The binary number representation has dominated digital logic for decades due to its compact storage requirements. An alternative representation is the unary number system: We use N bits, from which the first M are 1 and the rest are 0 to represent the value M/N . One-hot representation is a variation of the unary number system where it has one 1 in the N bits, where the 1’s position represents its value. We present a novel method that first converts binary numbers to unary using thermometer (one-hot) encoders and then uses a “scaling network” followed by voting gates that we call “alternator logic,” followed by a decoder to convert the numbers back to the binary format. For monotonically increasing functions, the scaling network is all we need, which essentially uses only the routing resources and flip-flops on a typical FPGA architecture. Our method is clearly superior to the conventional binary implementation: Our area×delay cost is on average only 0.4%, 4%, and 39% of the binary method for 8-, 10-, and 12-bit resolutions, respectively, in thermometer encoding scheme, and 0.5%, 15%, and 147% in the one-hot encoding scheme. In terms of power efficiency, our one-hot method is between about 69× and 114× better compared to conventional binary.

Let $\mathcal M=(M, be a linearly ordered first-order structure and T its complete theory. We investigate conditions for T that could guarantee that $\mathcal M$ is not much more complex than some colored orders (linear orders with added unary predicates). Motivated by Rubin’s work [5], we label three conditions expressing properties of types of T and/or automorphisms of models of T. We prove several results which indicate the “geometric” simplicity of definable sets in models of theories satisfying these conditions. For example, we prove that the strongest condition characterizes, up to definitional equivalence (inter-definability), theories of colored orders expanded by equivalence relations with convex classes.

Nonlinear optical (NLO) materials have critically important applications in advanced laser technologies. However, achieving a good balance between the mutual competing NLO properties and band gap w...

Raphael Robinson showed that all primitive recursive functions depending on one argument, and only they could be obtained from two functions s ( x ) = x +1 and q ( x ) = x - [√ x ]² by using operations of addition +, superposition ∗ and iteration i . Julia Robinson proved that from the same two functions, using the addition +, superposition ∗ and operation ¯¹ of function inversion, one could obtain all general recursive functions (under a certain condition on the inversion operation) and all partially recursive functions. On the basis of these results, A. I. Maltsev brought into consideration the Raphael Robinson algebra of all unary primitive recursive functions and two Julia Robinson algebras: the partial algebra of all unary general recursive functions and the algebra of all unary partially recursive functions and proposed to study the properties of these algebras, including the question of the existence of finite bases of identities in these algebras. In this article we show that there is no finite basis of identities in any of the indicated algebras.

We study an order scheduling problem with rejection, in which each order consists of multiple product types and each product type should be manufactured on a dedicated machine. The aim is to find a solution to minimize a linear sum of the maximum delivery completion time of the accepted orders and the total penalty of the rejected orders. Even if the delivery times of all orders are zero, the problem is shown to be binary $$\mathcal{NP}$$ -hard in the two-machine case and it is shown to be unary $$\mathcal{NP}$$ -hard when the number of machines is arbitrary. Three approximation algorithms are proposed and their worst-case performance ratios are analyzed. For the scenario where the number of machines is fixed, a pseudo-polynomial dynamic programming algorithm and a fully polynomial time approximation scheme are devised for it.

Melanin influences light reflection and absorption and is known to be one of the elements producing structural color, such as that in the feathers of birds. In this study, we used polydopamine (PDA), an artificial melanin, as a light-absorbing material and examined in detail the effect of its composite method on the structural color. The following two composite methods were investigated using cerium(IV) oxide (CeO2) particles as a core particle: binary coassembly of CeO2 and PDA particles and unary assembly of CeO2@PDA core-shell particles. Although both methods dramatically improved the visibility of the structural color by suppressing the scattered light owing to the light absorption capability of the PDA, there was a difference in the particle arrangement, angle dependence of the structural color, and color tone change. By selecting the PDA composite method, the guidelines for providing high visibility and the desired structural color were presented.

We consider algebraic systems with several products, including unary products, S (as examples we can take linear spaces, algebras, superalgebras, hom-algebras, triple systems, hom-triple systems, P...

We study two simple yet general complexity classes, which provide a unifying framework for efficient query evaluation in areas like graph databases and information extraction, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting and uniform generation of solutions, and show that they have several desirable properties in this respect. Both complexity classes are defined in terms of non deterministic logarithmic-space transducers (NL transducers). For the first class, we consider the case of unambiguous NL transducers, and we prove constant delay enumeration, and both counting and uniform generation of solutions in polynomial time. For the second class, we consider unrestricted NL transducers, and we obtain polynomial delay enumeration, approximate counting in polynomial time, and polynomialtime randomized algorithms for uniform generation. More specifically, we show that each problem in this second class admits a fully polynomial-time randomized approximation scheme (FPRAS) and a polynomial-time Las Vegas algorithm (with preprocessing) for uniform generation. Remarkably, the key idea to prove these results is to show that the fundamental problem #NFA admits an FPRAS, where #NFA is the problem of counting the number of strings of length n (given in unary) accepted by a non-deterministic finite automaton (NFA). While this problem is known to be #P-complete and, more precisely, SpanL-complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem, and obtain as a welcome corollary that every function in SpanL admits an FPRAS.

This article presents a piecewise linear approximation computation (PLAC) method for all nonlinear unary functions, which is an enhanced universal and error-flattened piecewise linear (PWL) approximation approach. Compared with the previous methods, PLAC features two main parts, an optimized segmenter to seek the minimum number of segments under the predefined software maximum absolute error (MAE), raising the segmentation performance to the highest theoretical level for logarithm, and a novel quantizer to completely simulate the hardware behavior and determine the required bit width and ${\text {MAE}}_{c}$ (MAE in circuits) for hardware implementation. In addition, the hardware architecture is also improved by simplifying the indexing logic, leading to nonredundant hardware overhead. The ASIC implementation results reveal that the proposed PLAC can improve all metrics without any compromise. Compared with the state-of-the-art methods, when computing logarithmic function, PLAC reduces 2.80% area, 3.77% power consumption, and 1.83% ${\text {MAE}}_{c}$ with the same delay; when approximating hyperbolic tangent function, PLAC reduces 6.25% area, 4.31% power consumption, and 18.86% ${\text {MAE}}_{c}$ with the same delay; when evaluating sigmoid function, PLAC reduces 16.50% area, 4.78% power consumption with the same delay, and ${\text {MAE}}_{c}$ ; and when calculating softsign function, PLAC reduces 17.28% area, 11.34% power consumption, 12.50% delay, and 33.28% ${\text {MAE}}_{c}$ .

Theory of completeness is essential for multi-valued logical functions. Using semi-tensor product (STP) of matrices, the algebraic form of k-valued logical functions is presented. Using algebraic form, a method is proposed to construct an adequate set of connectives (ASC), consisting of unary operators with conjunction/disjunction for k-valued logical functions, which can be used to express any k-valued logical functions. Based on it, two normal forms of k-valued logical functions are presented, which are extensions of the disjunctive normal form and conjunctive normal form of Boolean functions respectively. The ASC is then simplified to a condensed set. Finally, the normal forms are further extended to mix-valued logical functions.

We consider two kinds of reducibilities on finite families of predicates on a countable set: the definability of predicates and their complements of one family via another by means of existential formulas with parameters and the same definability on isomorphism types of families. Ordered structures of degrees generated by families of unary predicates are described. It is proved that for both reducibilities, there exist continuum many minimal nonzero degrees.

A positive definite Hermitian lattice is said to be 1-universal if it represents all positive definite unary Hermitian lattices, including both free and non-free Hermitian lattices. This paper is more concerned with the representations of unary non-free Hermitian lattices by Hermitian lattices. We estimate the minimal rank $$u_m^1$$ of 1-universal Hermitian lattices and we classify all 1-universal binary and ternary Hermitian lattices over imaginary quadratic fields $$\mathbb {Q}(\sqrt{-m})$$ for all positive square-free integers m.

We investigate the scheduling problem on a single bounded parallel-batch machine where jobs belong to two non-disjoint agents (called agent A and agent B) and are of equal length but different size. Each job’s size can be arbitrarily split into two parts and processed in the consecutive batches. It is permitted to process the jobs from different agents in a common batch. We show that it is unary NP-hard for the problem of minimizing the total weighted completion time of the jobs of agent A subject to the maximum cost of the jobs of agent B being upper bounded by a given threshold. For the case of the jobs of agent A having identical weights, we study the version of Pareto problem, and give a polynomial-time algorithm to generate all Pareto optimal points and a Pareto optimal schedule corresponding to each Pareto optimal point.

Demonic composition is defined on the set of binary relations over the non-empty set X, $$Rel_X$$ , and is a variant of standard or “angelic” composition. It arises naturally in the setting of the theory of non-deterministic computer programs, and shares many of the nice features of ordinary composition (it is associative, and generalises composition of functions). When equipped with the operations of demonic composition and domain, $$Rel_X$$ is a left restriction semigroup (like $$PT_X$$ , the semigroup of partial functions on X), whereas usual composition and domain give a unary semigroup satisfying weaker laws. By viewing $$Rel_X$$ under a restricted version of its usual composition and domain as a constellation (a kind of “one-sided” category), we show how this demonic left restriction semigroup structure arises on $$Rel_X$$ , placing it in a more general context. The construction applies to any unary semigroup with a “domain-like” operation satisfying certain minimal conditions which we identify. In particular it is shown that using the construction, any Baer $$*$$ -semigroup S can be given a left restriction semigroup structure which is even an inverse semigroup if S is $$*$$ -regular. It follows that the semigroup of $$n\times n$$ matrices over the real or complex numbers is an inverse semigroup with respect to a modified notion of product that almost always agrees with the usual matrix product, and in which inverse is pseudoinverse (Moore–Penrose inverse).