A strong Mal’cev condition for locally finite varieties omitting the unary type

We show that a finite algebra has a Taylor operation if and only if it has an operation satisfying a particular set of 6-ary Taylor identities. As a consequence we get the first strong Mal’cev condition for the family of locally finite varieties omitting the unary type. This is of interest to combinatorialists, as it is conjectured that a Constraint Satisfaction Problem defined by a core relational structure is polynomial time solvable exactly when a certain associated variety omits the unary type. Our result implies that the problem of deciding if a core relational structure meets this characterisation is itself in NP.     

工件具有加工位置上限最小化加权总误工量的单机排序问题

考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件J_j都具有一个加工位置上限k_j.也就是说,如果工件J_j是一个可行排序中的第x个工件,那么就需要满足x ≤ k_j.证明了（i）当工件具有相同工期时,该排序问题是二元NP-难的并且是拟多项式时间可解的,（ii）当工件具有单位权重时,该排序问题是一元NP-难的.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

On weighted multiway cuts in trees

A min—max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. We describe a dynamic programming type algorithm for this more general problem from biology and show that our min—max theorem does not apply to it.Corresponding author.Research of the author was supported by the A. v. Humboldt-Stiftung and the U.S. Office of Naval Research under the contract N-0014-91-J-1385.     

VLSI Circuit Performance Optimization by Geometric Programming

Delay of VLSI circuit components can be controlled by varying their sizes. In other words, performance of VLSI circuits can be optimized by changing the sizes of the circuit components. In this paper, we define a special type of geometric program called unary geometric program. We show that under the Elmore delay model, several commonly used formulations of the circuit component sizing problem considering delay, chip area and power dissipation can be reduced to unary geometric programs. We present a greedy algorithm to solve unary geometric programs optimally and efficiently. When applied to VLSI circuit component sizing, we prove that the runtime of the greedy algorithm is linear to the number of components in the circuit. In practice, we demonstrate that our unary-geometric-program based approach for circuit sizing is hundreds of times or more faster than other approaches.     

Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time

We consider the classical two-machine flow-shop scheduling for minimizing the total weighted completion time. For this problem, the computational complexity of a version in which the jobs have a common processing time on the second machine, has not been addressed. We show that the problem is unary NP-hard, answering an open problem posed in Zhu et al. (2016). Then we present an approximation algorithm for the problem with worst-case performance ratio at most 2.     

The complexity of isomorphism for complete theories of linear orders with unary predicates

Suppose A is a linear order, possibly with countably many unary predicates added. We classify the isomorphism relation for countable models of \(\text {Th}(A)\) up to Borel bi-reducibility, showing there are exactly five possibilities and characterizing exactly when each can occur in simple model-theoretic terms. We show that if the language is finite (in particular, if there are no unary predicates), then the theory is \(\aleph _0\)-categorical or Borel complete; this generalizes a theorem due to Schirmann (Theories des ordres totaux et relations dequivalence. Master’s thesis, Universite de Paris VII, 1997).     

All clones are centralizer clones

We show that any clone without virtual constants is isomorphic to the centralizer clone of a unary universal algebra, and that adding one unary relation to these unary algebras produces algebraic systems representing any clone.     

Constructing a perfect matching is in random NC

We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. We also show that several related problems lie in Random NC. These include:

1. Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation;
2. Constructing a maximum-cardinality matching;
3. Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary;
4. Constructing a maximums-t flow in a directed graph whose edge weights are given in unary.

     

Subalgebras of FA-presentable algebras

Automatic presentations, also called FA-presentations, were introduced to extend finite model theory to infinite structures whilst retaining the solubility of fundamental decision problems. This paper studies FA-presentable algebras. First, an example is given to show that the class of finitely generated FA-presentable algebras is not closed under forming finitely generated subalgebras, even within the class of algebras with only unary operations. In contrast, a finitely generated subalgebra of an FA-presentable algebra with a single unary operation is itself FA-presentable. Furthermore, it is proven that the class of unary FA-presentable algebras is closed under forming finitely generated subalgebras and that the membership problem for such subalgebras is decidable.     

Monoid intervals in lattices of clones

Suppose A is a finite set. For every clone C over A, the family C⁽¹⁾ of all unary functions in C is a monoid of transformations of the set A. We study how the lattice of clones is partitioned into intervals, where two clones belong to the same partition iff they have the same monoids of unary functions. The problem of Szendrei concerning the power of such intervals is investigated. We give new examples of intervals which are continual, one-element, and finite but not one-element. Moreover, it is proved that every lattice that is not more than a direct product of countably many finite chains is isomorphic to some interval in the lattice of clones, establishing, in passing, the number of E-minimal algebras on a finite set. Translated fromAlgebra i Logika, Vol. 34, No. 3, pp. 288-310, May-June, 1995.     

Free involutive Hom-semigroups and Hom-associative algebras

We construct free Hom-semigroups when its unary operation is multiplicative and is an involution. Our method of construction is by bracketed words. As a consequence, we obtain free Hom-associative algebras generated by a set under the same conditions for the unary operation.     

Scheduling in robotic cells: Complexity and steady state analysis

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. We focus on complexity issues and steady state performance. In a three machine cell producing multiple part-types, we prove that in two out of the six potentially optimal robot move cycles for producing one unit, the recognition version of the part sequencing problem is unary NP-complete. The other four cycles have earlier been shown to define efficiently solvable part 'sequencing problems. The general part sequencing problem not restricted to any robot move cycle in a three machine cell is shown to be unary NP-complete. Finally, we discuss the ways in which a robotic cell converges to a steady state.     

Binary homomorphisms and natural dualities

We investigate ways in which certain binary homomorphisms of a finite algebra can guarantee its dualisability. Of particular interest are those binary homomorphisms which are lattice, flat-semilattice or group operations. We prove that a finite algebra which has a pair of lattice operations amongst its binary homomorphisms is dualisable. As an application of this result, we find that every finite unary algebra can be embedded into a dualisable algebra. We develop some general tools which we use to prove the dualisability of a large number of unary algebras. For example, we show that the endomorphisms of a finite cyclic group are the operations of a dualisable unary algebra.     

On Some Monogenic Semigroups with an Associate Subgroup

Let S be any semigroup and a, s ∈ S. If a = asa, then s is an associate of a. A subgroup G of S is an associate subgroup of S if every a ∈ S has a unique associate a* in G. It turns out that G = H _z for some idempotent z, the zenith of S. The mapping a → a* is a unary operation on S. We say that S is monogenic if S is generated, as a unary semigroup, by a single element.

We embark upon the problem of the structure of monogenic semigroups in this sense by characterizing monogenic ones belonging to completely simple semigroups, normal cryptogroups, orthogroups, combinatorial semigroups, cryptic medial semigroups, cryptic orthodox semigroups, and orthodox monoids. In each of these cases, except one, we construct a free object. The general problem remains open.     

Perturbation Theory for Density Matrices and the Thermodynamic Potential of a Quantum System

We use the generating functional method for the matrix elements of second quantization operators to obtain a high-temperature expansion of the thermodynamic potential of a quantum system. This method permits isolating irreducible parts of matrices, including the particle-density matrices. We derive an equation for the full unary density matrix, which is equivalent to the variational principle for the thermodynamic potential. The thermodynamic functions and the density matrix can thus be found in the framework of the same variational problem.     

Group-universal unary varieties

LetV be a variety of unary algebras and letM(V) be the monoid of all unary polynomials ofV. Then every group appears as the automorphism group of an algebraA∈V if and only if the left ideals ofM(V) do not form an inclusion-ordered chain. The support of the National Research Council of Canada is gratefully acknowledged. Presented by J. Mycielski.     

A polynomial characterization of congruence classes

Let be a regular and permutable variety and . Let . We get an explicit list L of polynomials such that C is a congruence class of some iff C is closed under all terms of L. Moreover, if is a finite similarity type, L is finite. If also is finite, all polynomials of L can be considered to be unary. We get a formula for the estimation of card L. The problem of deciding whether C is a congruence class of a finite algebra is in NP but for it is in P. Received May 24, 1996; accepted in final form November 26, 1996.     

Homomorphic images of finite subdirectly irreducible unary algebras

We prove that a finite unary algebra with at least two operation symbols is a homomorphic image of a (finite) subdirectly irreducible algebra if and only if the intersection of all its subalgebras which have at least two elements is nonempty. While working on this paper the first and the third authors were partially supported by the Grant Agency of the Czech Republic, grant #201/02/0594, and by the institutional grant MSM0021620839; the second author was supported by the Ministry of Science, Technologies and Development of Republic of Serbia, grant no. 1227.