首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Inequivalence of finite automata accepting finite languages over a non-unary alphabet is NP-complete. However, the inequality of their behaviors does not appear to have been carefully investigated. In the simplest case, the behavior of a finite automaton is the formal series f such that the coefficient f(w) of a word w is the number of distinct accepting computations on w. This notion will be generalized in the paper to finite automata with rational weights. The main result is that inequality of rational weight finite automata with finite behaviors is in R, random polynomial time.  相似文献   

2.
We investigate weighted automata with discounting and their behaviors over semirings and finitely generated graded monoids. We characterize the discounted behaviors of weighted automata precisely as rational formal power series with a discounted form of the Cauchy product. This extends a classical result of Kleene-Schützenberger. Here we show that the very special case of Schützenberger's result for free monoids over singleton alphabets suffices to deduce our generalization.  相似文献   

3.
A power series r with noncommuting variables is called Parikh simple if no two words in the support of r are commutatively equivalent. We show that equality is decidable for Parikh simple algebraic power series having their coefficients in a computable field.  相似文献   

4.
The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in [J.H. Conway, Regular Algebra and Finite Machines, Chapman Hall, 1971], whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc [M. Kunc, The power of commuting with finite sets of words, in: Proc. of STACS 2005, in: LNCS, vol. 3404, Springer, 2005, pp. 569–580], a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.  相似文献   

5.
A recognizable series over the semiring of the integers is a function that maps each word over an alphabet to an integer. The support of such a series consists of all those words which are not mapped to zero. It is long known that there are recognizable series whose support is not a recognizable, but a context-free language. However, the problem of deciding whether the support of a given recognizable series is recognizable was never considered. Here we show that this problem is undecidable. The proof relies on an encoding of an instance of Post?s correspondence problem.  相似文献   

6.
We show that the class of HDT0L sequences is closed with respect to total rational functions.  相似文献   

7.
We solve a problem raised by Boasson [5] concerning the language B*1 = s{;xn(y+x+)*yn vb; n ? 1s};*. We prove that t he rational cone generated by B*1 which is closed under product but not under the star operation [5] does not contain any non-rational AFL.  相似文献   

8.
Agent based computing is generally intended for modeling and implementation of distributed complex problems. Despite the existence of many applications, the problem of rational engineering of multi-agent systems remains complex and difficult. The purpose of this paper can be summarized within two claims. First, we aim at providing an approach that gives some guidelines for specifying and designing multi-agent systems. Secondly, we focus on the formalisms as a language for describing the models produced in each development process phases. These seem to be straightforward, while the development of multi-agent systems is still done, in most cases, without using methods and formal modeling such as those generally used in object oriented software. We illustrate this approach by specifying an example based upon a specific agent architecture.  相似文献   

9.
The correct functioning of interactive computer systems depends on both the faultless operation of the device and correct human actions. In this paper, we focus on system malfunctions due to human actions. We present abstract principles that generate cognitively plausible human behaviour. These principles are then formalised in a higher-order logic as a generic, and so retargetable, cognitive architecture, based on results from cognitive psychology. We instantiate the generic cognitive architecture to obtain specific user models. These are then used in a series of case studies on the formal verification of simple interactive systems. By doing this, we demonstrate that our verification methodology can detect a variety of realistic, potentially erroneous actions, which emerge from the combination of a poorly designed device and cognitively plausible human behaviour.  相似文献   

10.
Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve recognizability, generalizing the recent results of Zhang [16] to the formal power series setting. We show, for example, that the “square-root” operation, while preserving regularity for formal languages, preserves recognizability for formal power series when the underlying semiring is commutative or locally finite, but not in general.  相似文献   

11.
We define a weighted monadic second order logic for trees where the weights are taken from a commutative semiring. We prove that a restricted version of this logic characterizes the class of formal tree series which are accepted by weighted bottom-up finite state tree automata. The restriction on the logic can be dropped if additionally the semiring is locally finite. This generalizes corresponding classical results of Thatcher, Wright, and Doner for tree languages and it extends recent results of Droste and Gastin [Weighted automata and weighted logics, in: Automata, Languages and Programming—32nd International Colloquium, ICALP 2005, Lisbon, Portugal, 2005, Proceedings, Lecture Notes in Computer Science, Vol. 3580, Springer, Berlin, 2005, pp. 513–525, full version in Theoretical Computer Science, to appear.] from formal power series on words to formal tree series.  相似文献   

12.
A Faà di Bruno type Hopf algebra is developed for a group of integral operators known as Fliess operators, where operator composition is the group product. Such operators are normally written in terms of generating series over a noncommutative alphabet. Using a general series expansion for the antipode, an explicit formula for the generating series of the compositional inverse operator is derived. The result is applied to analytic nonlinear feedback systems to produce an explicit formula for the feedback product, that is, the generating series for the Fliess operator representation of the closed-loop system written in terms of the generating series of the Fliess operator component systems. This formula is employed to provide a proof that local convergence is preserved under feedback.  相似文献   

13.
A rational expansion for non-linear input-output maps is introduced. This new method is based on the rational expansion of functions of several complex variables. If truncated, this series reduces to a ratio of truncated Volterra series. A 'feedback form' is presented.  相似文献   

14.
The developmental process of a multicellular organism is considered as a series of graphs, whose nodes correspond to cells, and edges to cellular interconnections. We introduce here a new mechanism, called a rational machine, for generating series of finite directed graphs. With biological applications in mind, each node is named with a string of symbols. First the growth rate of graphs is analyzed. The generative capability of a rational machine is shown with many examples. Decision problems and closure properties under operations are also discussed. Among other things, it is shown that whether two rational machines generate the same graph series is undecidable.  相似文献   

15.
李璐  张大明  刘华勇 《计算机工程》2010,36(17):226-227,231
为实现多个多边形间的平滑自然渐变,提出基于二元混合向量值有理插值的非线性二维形状渐变方法。将多个多边形的顶点坐标作为平面域上的向量,利用二元Newton-Thiele型向量连分式建立有理插值曲面,通过对插值曲面进行重采样得到一系列渐变中间多边形。实验结果表明,该方法具有计算精度高、适应性强、易于编程实现的特点。  相似文献   

16.
李燕 《计算机科学》2006,33(1):202-204
DNA计算是应用分子生物技术进行计算的新方法。从理论上研究DNA计算方法,有利于推动理论计算科学的发展。本系列文章应用形式语言及自动机理论技术,系统地探讨了DNA分子的可计算性及其计算能力。本文主要介绍常用DNA分子操作方法,并根据DNA分子的结构及特点,给出了DNA分子的形式化描述。  相似文献   

17.
Given a Feynman parameter integral, depending on a single discrete variable NN and a real parameter εε, we discuss a new algorithmic framework to compute the first coefficients of its Laurent series expansion in εε. In a first step, the integrals are expressed by hypergeometric multi-sums by means of symbolic transformations. Given this sum format, we develop new summation tools to extract the first coefficients of its series expansion whenever they are expressible in terms of indefinite nested product–sum expressions. In particular, we enhance the known multi-sum algorithms to derive recurrences for sums with complicated boundary conditions, and we present new algorithms to find formal Laurent series solutions of a given recurrence relation.  相似文献   

18.
In the problem area of evaluating complex software systems, there are two distinguished areas of research, development, and application identified by the two buzzwords validation and verification, respectively. From the perspective adopted by the authors, verification is usually more formally based and, thus, can be supported by formal reasoning tools like theorem provers, for instance. The scope of verification approaches is limited by the difficulty of finding a sufficiently complete formalization to build upon. In paramount realistic problem domains, validation seems to be more appropriate, although it is less stringent in character and, therefore, validation results are often less definite. The aim of this paper is to exemplify a validation approach based on a clear and thoroughly formal theory. In this way, validation and verification should be brought closer to each other. To allow for precise and sufficiently clear results, the authors have selected the application domain of algorithms and systems for learning formal languages. By means of the validation toolkit TIC, some series of validation experiments have been performed. The results are presented for the sake of illustrating the underlying formal concepts in use. Comparing the validity of one learning approach to the invalidity of another one can be seen as an interesting result in its own right.  相似文献   

19.
This paper addresses real-time decision-making associated with acoustic measurements for online surveillance of undersea targets moving over a deployed sensor network. The underlying algorithm is built upon the principles of symbolic dynamic filtering for feature extraction and formal language theory for decision-making, where the decision threshold for target detection is estimated based on time series data collected from an ensemble of passive sonar sensors that cover the anticipated tracks of moving targets. Adaptation of the decision thresholds to the real-time sensor data is optimal in the sense of weighted linear least squares. The algorithm has been validated on a simulated sensor-network test-bed with time series data from an ensemble of target tracks.  相似文献   

20.
We consider the following decision problem: given a finite Markov chain with distinguished source and target states, and given a rational number r, does there exist an integer n such that the probability to reach the target from the source in n steps is r? This problem, which is not known to be decidable, lies at the heart of many model checking questions on Markov chains. We provide evidence of the hardness of the problem by giving a reduction from the Skolem Problem: a number-theoretic decision problem whose decidability has been open for many decades.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号