首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 156 毫秒
1.
A synchronizing word for a given synchronizing DFA is called minimal if none of its proper factors is synchronizing. We characterize the class of synchronizing automata having only finitely many minimal synchronizing words (the class of such automata is denoted by FG). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3n-5. We also prove that checking whether a given DFA A is in FG is co-NP-hard and provide an algorithm for this problem which is exponential in the number of states A.  相似文献   

2.
We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is specified by a regular set of target configurations and a qualitative probability constraint ‘>0’ or ‘=1’. The goal of one player is to maximize the probability of reaching the target set so that the constraint is satisfied, while the other player aims at the opposite. We show that the winner in such games can be determined in P for the ‘>0’ constraint, and in NPco-NP for the ‘=1’ constraint. Further, we prove that the winning regions for both players are regular, and we design algorithms which compute the associated finite-state automata. Finally, we show that winning strategies can be synthesized effectively.  相似文献   

3.
We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The different problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete (when they are not trivial). We also consider alternative achievement and maintenance agent design problems by allowing longer runs in environments (that is, our environments are bounded but the bounds are more liberal than was the case previously). Again, we obtain a complete classification but so that the different problems are DEXPTIME-complete, NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACE-complete (when they are not trivial).  相似文献   

4.
A strategy for dual sensing of Na+ and K+ ions using Prussian blue nanotubes via selective inter/deintercalation of K+ ion and competitive inhibition by Na+ ion, is reported. The analytical signal is derived from the cyclic voltammetry cathodic peak position Epc of Prussian blue nanotubes. Na+ and K+ levels in a sample solution can be determined conveniently using one Prussian blue nanotubes sensor. In addition, this versatile method can be applied for the analysis of single type of either Na+ or K+ ions. The dual-ion sensor response towards Na+ and K+ can be described using a model based on the competitive inhibition effects of Na+ on K+ inter/deintercalation in Prussian blue nanotubes. Successful application of the Prussian blue nanotubes sensor for Na+ and K+ determination is demonstrated in artificial saliva.  相似文献   

5.
In current feature-based parametric design systems, the reusability principle is not fully supported as it was expected. Unpredictability and ambiguity of models often happen during design modification within one system as well as among different systems. This reference deficiency significantly reduces the power of feature-based parametric modeling, where geometry re-evaluation generates unexpected shapes. In this paper, a sufficient condition of B-Rep variance based on geometry continuity in parametric complex Euclidean (PpC3) space is proposed. Shape and relation parameters are differentiated in PpC3, thus parametric family can be defined. A semantic id scheme based on continuity of geometry is developed to solve the problem of naming persistency and to improve interoperability of CAD feature modeling. Hierarchical namespaces localize entity creation and identification. All geometric and topological entities are referred uniformly based on surface ids, and topology semantics is retained in id itself.  相似文献   

6.
Learning complex action models with quantifiers and logical implications   总被引:1,自引:0,他引:1  
Automated planning requires action models described using languages such as the Planning Domain Definition Language (PDDL) as input, but building action models from scratch is a very difficult and time-consuming task, even for experts. This is because it is difficult to formally describe all conditions and changes, reflected in the preconditions and effects of action models. In the past, there have been algorithms that can automatically learn simple action models from plan traces. However, there are many cases in the real world where we need more complicated expressions based on universal and existential quantifiers, as well as logical implications in action models to precisely describe the underlying mechanisms of the actions. Such complex action models cannot be learned using many previous algorithms. In this article, we present a novel algorithm called LAMP (Learning Action Models from Plan traces), to learn action models with quantifiers and logical implications from a set of observed plan traces with only partially observed intermediate state information. The LAMP algorithm generates candidate formulas that are passed to a Markov Logic Network (MLN) for selecting the most likely subsets of candidate formulas. The selected subset of formulas is then transformed into learned action models, which can then be tweaked by domain experts to arrive at the final models. We evaluate our approach in four planning domains to demonstrate that LAMP is effective in learning complex action models. We also analyze the human effort saved by using LAMP in helping to create action models through a user study. Finally, we apply LAMP to a real-world application domain for software requirement engineering to help the engineers acquire software requirements and show that LAMP can indeed help experts a great deal in real-world knowledge-engineering applications.  相似文献   

7.
So far, the four-arc approximations to an ellipse E are made under the condition that the major and minor axes keep strictly unchanged. In general, however, this condition is unnecessary. Then the fitting can be further improved. Considering a representative quadrant of E, we first draw two auxiliary circular arcs tangent to E at the axes but having a gap ε at their boundary, such that the small arc S lies outside the large arc L. Meanwhile the extreme errors of S and L w.r.t. E are ε and −ε respectively. Giving the radii of S and L a decrement −ε/2 and an increment ε/2 brings them to join smoothly. Thus, reducing the overall error to minimum, an analytic solution in implicit form is derived.  相似文献   

8.
Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +ε)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +ε)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +ε)-approximation algorithm for an MWCDS.  相似文献   

9.
Two salicylaldehyde based colorimetric and fluorescent chemosensors 1 and 2 were developed. Both receptors 1 and 2 showed unique selectivity for the fluoride anions over other anions in DMSO solution. [TBA] OH and 1H NMR titration experiments revealed that the F-induced colorimetric and “turn on” fluorescence response were driven by hydrogen bonding interaction between the OH protons and F.  相似文献   

10.
We develop an algorithmic, metaheuristic approach to the definition of molecule-fixed axes orientation in molecules of arbitrary size. The goal is to simplify the treatment of overall rotation and rotation-vibration interaction in rovibrational Hamiltonians. Considering the kinetic elements of the rovibrational Hamiltonian, given by the G matrix, we select the optimal orientation of molecule-fixed axes minimizing specific G matrix elements. To such an end, we develop a global minimization method based in a hybrid Simulated Annealing+Powell's local minimization. The parameters of the method are calibrated using a set of non-rigid molecules: Acetaldehyde, glycolaldehyde, methyl formate and ethyl methyl ether. The results show that the principal axes of inertia do not give the simplest form to the pure rotational contribution. However, minimization of the G matrix rotational element does. Finally, we observe that in the cases considered it is not possible to nullify all the rotation-vibration coupling elements, since the torsional motions are coupled with the overall rotation. However, the treatment yields the optimal solution. The methodology proposed allows also to simplify simultaneously the pure rotational+rotation-vibration coupling elements in rovibrational Hamiltonians.  相似文献   

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

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