Computational complexity of some problems involving congruences on algebras

We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.     

Reasoning about Qualitative Spatial Relationships

In this paper, we consider various spatial relationships that are of general interest in pictorial database systems and other applications. We present a set of rules that allow us to deduce new relationships from a given set of relationships. A deductive mechanism using these rules can be used in query-processing systems that retrieve pictures by content. The given set of rules is shown to be sound; that is, the deductions are logically correct. The rules are also shown to be complete for three-dimensional systems; that is, every relationship that is implied by a given consistent set of relationships F is deducible from F using the given rules. In addition, we show that the given set of rules is incomplete for two-dimensional systems. We also present efficient algorithms for the deduction and reduction problems. The deduction problem consists of computing all the relationships deducible from a given set, while the reduction problem consists of computing a minimal subset of a given set of relationships that implies all the relationships in the given set.     

(A, B)-invariant and stabilizability subspaces, a frequency domain description

In a paper of E. Emre and the author a polynomial characterization for (A, B)-invariant subspaces is given. The characterization is used to give a frequency domain criterion for the solvability of the disturbance decoupling problem. In this paper a more elementary and simpler treatment is given. Furthermore, stabilizability subspaces are introduced, are given a frequency domain characterization and are used to solve design problems.     

三对角对称矩阵逆特征问题存在唯一解的条件

n阶实对称矩阵称为n阶三对角对称矩阵,全体记为S0,若：i）b;＞0（i二1,2,…,l－1）称T为J。C0bi矩阵,全体记为SI;11）h＜0（d一1;又…,n－1）称T为负JacoN矩阵,全体记为h;iii）b;一叩一1,2,…,n－1）称T为不可约三对角对称矩阵,全体记为龙Jacobi矩阵的逆特征问题有广泛的应用;近年来有了较大发展［‘,’］．对由二个特征对构造相应的Jacobi矩阵或三对角对称矩阵问题的研究相对地比较成熟I’一义而对由三个特征对构造相应的Jacobi矩阵或三对角对称矩阵问题的研究却进展迟缓．文门对此作了一些尝试,本文具体研究：…     

The multiple phase service network with generalized processor sharing

Summary An analysis is given of multiple phase service facilities of which queueing networks are special models, for the case of a service discipline to be denoted as generalized processor sharing. Under this discipline requests are served simultaneously with a rate depending on the phase and the number of requests present here. The model is of a very general type, its analysis is given for arbitrary routing matrices and absolutely continuous required service time distributions. The mathematical technique used is that of the supplementary variable. Generalisations of known results for closed and open networks are obtained and new results about the average sojourn time of a request in the system are derived, in particular for requests with given route and given processing times at the nodes of the route. Some basic results about reversed processes and departure processes are discussed. For a special but important model the workload is discussed.     

On feedback controllers

The two main results are the necessary and sufficient conditions for the existence of a causal and a strongly causal feedback controller which realizes a given behaviour on a given system. The proofs are constructive. If the given system is a discrete event system or an ordinary discrete event system, then a controller could also be a discrete event system or an ordinary discrete event system, respectively. The results are given using an algebraic approach to the modelling of general time systems introduced by the author.     

A method for recognizing and evaluating states of weakly formalized dynamic object based on labeling a time series

The problem of recognizing states of a complex dynamic object given by a stochastic time series is considered. A method of labeling a series and an algorithm implementing it are given. Conditions for existence of a correct solution are presented. Results of program simulation and solution of an applied problem are given.     

A non-linear system controller

A method is given for finding a feedback controller that forces the response of a given non-linear system to follow the response of a predetermined linear system. A test is provided that gives sufficient conditions for the existence of such a control. Algorithms are given that allow implementation on a digital computer. Possible solutions to some of the difficulties encountered in using this method are also investigated. Both the deterministic and stochastic cases are examined.     

Maximal and minimal representations of gapped and non-gapped motifs of a string

The problems of finding maximal and minimal equivalent representations for gapped and non-gapped motifs as well as finding motifs that characterize a fixed set of occurrence locations for a given string are studied. We apply two equivalence relations on representations. The first one is the well-known occurrence-equivalence of motifs. The second equivalence is introduced for patterns of occurrence locations, to characterize such patterns by motifs. For both equivalences, quadratic-time algorithms are given for finding a maximal representative of an equivalence class. Finding a minimal representative is shown to be NP-complete in both cases. For non-gapped motifs suffix-tree-based linear-time algorithms are given for finding maximal and minimal representatives. Maximal (minimal) gapped motifs are composed of blocks that are maximal (minimal) non-gapped motifs, maximal and minimal non-gapped motifs thus making up a small basis for all motifs. The implied bound on the number of gapped motifs that have a fixed number of non-gapped blocks is also given.     

A statistical minimax approach to optimizing linear models under a priori uncertainty conditions

A statistical minimax method for optimizing linear models with parameters, given up to the accuracy of belonging to some uncertainty sets, is proposed. Statistical methods for constructing uncertainty sets as confidence regions with a given reliability level are presented. A numerical method for finding a minimax strategy is proposed for arbitrary uncertainty sets that meet convexity and compactness conditions. A number of examples are considered that admit the analytical solution to optimization problem. Results of numerical simulation are given.     

SLR(1) and LALR(1) parsing for unrestricted grammars

Summary Simple LR(1) and lookahead LR(1) phrase structure grammars are defined and corresponding deterministic two-pushdown automata which parse all sentences are given. These grammars include a wide variety of grammars for non context-free languages. A given phrase structure grammar is one of these types if the parse table for the associated automaton has no multiple entries. A technique for construction of this parse table is given which in the lookahead case involves elimination of inverses in a grammar for lookahead strings for LR(0) items and computation of first sets for strings of symbols in the given grammar.     

模糊商空间理论(模糊粒度计算方法)

把商空间模型推广到模糊粒度世界,并给出了两个基本结论.一个结论是,下面4种提法等价:(1) 在论域X上给定一个模糊等价关系;(2) 给定X的商空间上的一个归一化等腰距离;(3) 给定X的一个分层递阶结构;(4) 给定一个X的模糊知识基.另一个结论是,所有模糊粒度世界全体,构成一个完备半序格.这些结论为粒度计算提供了一个强有力的数学模型和工具.     

Efficient and Robust Path Openings Using the Scale-Invariant Rank Operator

Some basic properties of a slightly generalized version of the scale-invariant rank operator are given, and it is shown how this operator can be used to create a nearly scale-invariant generalization of path openings that is robust to noise. Efficient algorithms are given for sequences and directed acyclic graphs with binary values, as well as sequences with real (greyscale) values. An algorithm is also given for directed acyclic graphs with real weights. It is shown that the given algorithms might be extended even further by allowing for scores based on a totally ordered semigroup.     

一类非线性系统观测器与算例

给出了非线性系统状态观测器的一种提法, 对所给非线性系统作了必要的假设. 对非线性系统状态观测器存在的条件进行了分析, 进而讨论了一类非线性系统观测器的构造方法, 并给出了算例.     

Lower and upper bounds on time for multiprocessor optimal schedules

The lower and upper bounds on the minimum time needed to process a given directed acyclic task graph for a given number of processors are derived. It is proved that the proposed lower bound on time is not only sharper than the previously known values but also easier to calculate. The upper bound on time, which is useful in determining the worst case behavior of a given task graph, is presented. The lower and upper bounds on the minimum number of processors required to process a given task graph in the minimum possible time are also derived. It is seen with a number of randomly generated dense task graphs that the lower and upper bounds we derive are equal, thus giving the optimal time for scheduling directed acyclic task graphs on a given set of processors     

加工时间扰动时－类排序问题的性能估计

研究一类排序问题的扰动分析。首先给出加工时间扰动时间顺序Ｆｍ／／Ｃｍａｘ问题的性能估计；然后，给出Ｊｏｈｎｓｏｎ排法的鲁棒条件，并给出ＷＳＰＴ排法具有鲁棒性的充要条件。     

离散时间系统下的积分二次约束方法的几个问题

研究了离散情形下的反馈系统的稳定性问题,利用新近发展起来的积分二次约束 (IQC)方法,对离散系统的反馈连接问题,给出了其稳定性分析准则和一些必要条件,这些结果 适用于时不变与时变系统.其次,利用已有的结果.得到了离散时变系统MIMO情况下的绝对 稳定性问题的一个判据.最后,利用一个较强的IQC定义,给出了判断某一类反馈系统稳定的 充分必要条件.     

Generation of random variates using asymptotic expansions

Monte-Carlo methods are widely used numerical tools in various fields of application, like rarefied gas dynamics, vacuum technology, stellar dynamics or nuclear physics. A central part is the generation of random variates according to a given probability law. Fundamental techniques are the inversion principle or the acceptance-rejection method—both may be quite time-consuming if the given probability law has a complicated structure. In this paper probability laws depending on a small parameter are considered and the use of asymptotic expansions to generate random variates is investigated. The results given in the paper are restricted to first order expansions. Error estimates for the discrepancy as well as for the bounded Lipschitz distance of the asymptotic expansion are derived. Furthermore the integration error for some special classes of functions is given. The efficiency of the method is proved by a numerical example from rarefied gas flows.     

三次有理Bézier曲线的形状调整方法

给出了两类调整三次有理Bézier曲线形状的方法。一类方法是使曲线通过给定的插值点,从而实现曲线的形状调整。另一类方法是将曲线上的点作为控制多边形两边连线段上的分点,通过调整分线段的比例,实现对曲线的形状调整。针对不同情况,分别给出了权因子的计算公式。计算方法简单,使用方便,并使三次有理Bézier曲线的形状调整更加具体和明确。同时,由计算结果得到了任意三次有理Bézier曲线不相交的充分必要条件。