幺半环上几类模糊自动机的关系

给出了幺半环上非确定的模糊自动机和确定的模糊自动机及其语言的定义,证明了幺半环上三类非确定的模糊自动机间的等价性和三类确定的模糊自动机间的等价性,讨论了幺半环上三类非确定的模糊自动机和第四类非确定的模糊自动机之间的关系,以及幺半环上非确定的模糊自动机和确定的模糊自动机之间的关系.     

A new algorithm of the state-minimization for the nondeterministic finite automata

The problem of the state-minimization for the nondeterministic finite Rabin-Scott’s automata is considered. A new algorithm for this problem is obtained. The obtained algorithm has the exponential effectiveness, like the earlier-known algorithms for this problem. But each of previous algorithms amounts to the search of minimum generative system for local reaction of equal automaton of canonical form, and unlike them, we use in this paper two special functions, marking states of the given automaton.     

Didactic approach for teaching nondeterminism in automata theory

Nondeterminism plays a central role in almost all fields of computer science. It has been incorporated naturally as well as in the theory of automata as a generalization of determinism. Although nondeterministic finite automata do not have more recognition power than deterministic ones their importance and usefulness is of no doubt.Unfortunately, the operation of the mathematical model of nondeterministic automata is difficult to understand which means a didactic challenge for every teacher and lecturer. This paper gives a didactic approach to introduce the notion of finite (deterministic and) nondeterministic automata.As a teaching tool we make use of the automata theory package developed in Maple. We put emphasis on the process character of learning and work out a method that promotes the repetitive experiments.     

A polynomial oracle-time algorithm for convex integer minimization

In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms.     

Shortest directing words of nondeterministic directable automata

In this paper, we will survey several results on the shortest directing words of various types of nondeterministic directable automata.¹     

PTIME Parametric Verification of Safety Properties for Reasonable Linear Hybrid Automata

This paper identifies an industrially relevant class of linear hybrid automata (LHA) called reasonable LHA for which parametric verification of convex safety properties with exhaustive entry states can be verified in polynomial time and time-bounded reachability can be decided in nondeterministic polynomial time for non-parametric verification and in exponential time for parametric verification. Properties with exhaustive entry states are restricted to runs originating in a (specified) inner envelope of some mode-invariant. Deciding whether an LHA is reasonable is shown to be decidable in polynomial time.     

Once more about the state-minimization of the nondeterministic finite automata

In this paper we consider the corrected version of the algorithm of the state-minimization for the nondeterministic finite automata: we correct here a mistake of the previous paper, where the same problem was considered.     

Scheduling jobs with position-dependent processing times

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.     

Finitely nonstationary nondeterministic automata with random input

Properties of generalized finitely nonstationary nondeterministic automata with an additional random input over a Boolean lattice are considered which are related to the definition of the class of languages represented by such automaton models. New notions of an elementary nondeterministic automatic structure with a random input, of a generalized finitely nonstationary nondeterministic automaton with a random input, of the generalized mapping induced by such an automaton, and of a generalized language represented by such an automaton are introduced. A number of statements substantiating synthesis for any given generalized finitely nonstationary nondeterministic automaton with a random input of an abstract probabilistic finite automaton equivalent to the given one relative to the represented generalized language probabilistic language of the stationary abstract probabilistic finite automaton. The number of states of the synthesized probabilistic automaton is estimated and a synthesis algorithm is developed in detail and illustrated by an example.     

Nondeterministic dynamic programming on a parallel coprocessing system

We describe how nondeterministic dynamic programming (DP) algorithms can be designed for a new class of parallel coprocessing systems using “functional memory”, an architecture based upon dataflow computer principles. We also show how Petri nets can be used to model and express such parallel DP algorithms. Finally, we discuss architectural improvements that would facilitate the processing of Petri net models of nondeterministic DP algorithms on functional memory computers (FMC).     

具有输出字符功能的模糊自动机的最小化问题

通过文献[8]中两类具有输出字符功能的Fuzzy自动机和Fuzzy有限状态自动机的强等价性,等价性和弱等价性的条件,在以往仅仅给出的Fuzzy有限状态自动机的最小化问题基础上,讨论了具有更广泛意义的具有输出字符功能的Fuzzy自动机的最小化问题,以及其最小化自动机与Fuzzy有限状态自动机的最小化自动机在不同条件下的关系。     

Another version of the proximal point algorithm in a Banach space

In this paper, we study some non-traditional schemes of proximal point algorithm for nonsmooth convex functionals in a Banach space. The proximal approximations to their minimal points and/or their minimal values are considered separately for unconstrained and constrained minimization problems on convex closed sets. For the latter we use proximal point algorithms with the metric projection operators and first establish the estimates of the convergence rate with respect to functionals. We also investigate the perturbed projection proximal point algorithms and prove their stability. Some results concerning the classical proximal point method for minimization problems in a Banach space is also presented in this paper.     

Eigenvalues and switching algorithms for Quasi-Newton updates

Two switching algorithms QNSWl and QNSW2 are proposed in this paper. These algorithms are developed based on the eigenvalues of matrices which are inertial to the symmetric rank-one (SR1) updates and the BFGS updates. First, theoretical results on the eigenvalues and condition numbers of these matrices are presented. Second, switch-ing mechanisms are then developed based on theoretical results obtained so that each proposed algorithm has the capability of applying appropriate updating formulae at each iterative point during the whole minimization process. Third, the performance of

each of the proposed algorithms is evaluated over a wide range of test problems with variable dimensions. These results are then compared to the results obtained by some well-known minimization packages. Comparative results show that among the tested methods, the QNSW2 algorithm has the best overall performance for the problems examined. In some cases, the number of iterations and the number function/gradient calls required by certain existing methods are more than a four-fold increase over that required by the proposed switching algorithms     

Bisimulations for fuzzy automata

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata A and B is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on A and B and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata A and B are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of A and B with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.     

Convexification and Concavification for a General Class of Global Optimization Problems

A kind of general convexification and concavification methods is proposed for solving some classes of global optimization problems with certain monotone properties. It is shown that these minimization problems can be transformed into equivalent concave minimization problem or reverse convex programming problem or canonical D.C. programming problem by using the proposed convexification and concavification schemes. The existing algorithms then can be used to find the global solutions of the transformed problems.     

Parallel Synchronous and Asynchronous Space-Decomposition Algorithms for Large-Scale Minimization Problems

Three parallel space-decomposition minimization (PSDM) algorithms, based on the parallel variable transformation (PVT) and the parallel gradient distribution (PGD) algorithms (O.L. Mangasarian, SIMA Journal on Control and Optimization, vol. 33, no. 6, pp. 1916–1925.), are presented for solving convex or nonconvex unconstrained minimization problems. The PSDM algorithms decompose the variable space into subspaces and distribute these decomposed subproblems among parallel processors. It is shown that if all decomposed subproblems are uncoupled of each other, they can be solved independently. Otherwise, the parallel algorithms presented in this paper can be used. Numerical experiments show that these parallel algorithms can save processor time, particularly for medium and large-scale problems. Up to six parallel processors are connected by Ethernet networks to solve four large-scale minimization problems. The results are compared with those obtained by using sequential algorithms run on a single processor. An application of the PSDM algorithms to the training of multilayer Adaptive Linear Neurons (Madaline) and a new parallel architecture for such parallel training are also presented.     

Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a unified approach

This paper focuses on some customized applications of the proximal point algorithm (PPA) to two classes of problems: the convex minimization problem with linear constraints and a generic or separable objective function, and a saddle-point problem. We treat these two classes of problems uniformly by a mixed variational inequality, and show how the application of PPA with customized metric proximal parameters can yield favorable algorithms which are able to make use of the models’ structures effectively. Our customized PPA revisit turns out to unify some algorithms including some existing ones in the literature and some new ones to be proposed. From the PPA perspective, we establish the global convergence and a worst-case O(1/t) convergence rate for this series of algorithms in a unified way.     

Parallel computing in nonconvex programming

In this paper, we are concerned with the development of parallel algorithms for solving some classes of nonconvex optimization problems. We present an introductory survey of parallel algorithms that have been used to solve structured problems (partially separable, and large-scale block structured problems), and algorithms based on parallel local searches for solving general nonconvex problems. Indefinite quadratic programming posynomial optimization, and the general global concave minimization problem can be solved using these approaches. In addition, for the minimum concave cost network flow problem, we are going to present new parallel search algorithms for large-scale problems. Computational results of an efficient implementation on a multi-transputer system will be presented.     

Exponential approximation schemata for some network design problems

We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled.