共查询到20条相似文献,搜索用时 31 毫秒
1.
Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton
and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of
. The transitivity equivalence of the subgroups of the automorphism group of
are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of
. We then characterize the automorphism group of
with respect to the maximal induced group. As an application, we show that, given a group G and an automaton
, there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is
. 相似文献
2.
Let
be a finite field withq elements and
a rational function over
. No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on
. The problem has been shown to be in co-R
co-NP, and in this paper we prove that it is inR
NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over
. Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented. 相似文献
3.
Let
be some set of orientations, that is,
. We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in
. We call such curves
-staircases. Two points p andq in a polygonP are said to
-see each other if an
-staircase fromp toq exists that is completely contained inP. The
-kernel of a polygonP is then the set of all points which
-see all other points. The
-kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with
. With the help of this observation we are able to develop an
algorithm to compute the
-kernel of a simple polygon, for finite
. We also show how to compute theexternal
-kernel of a polygon in optimal time
. The two algorithms are combined to compute the (
-kernel of a polygon with holes in time
.This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario. 相似文献
4.
Mohammad A. Shokrollahi 《Computational Complexity》1991,1(2):157-181
In the present paper we shall show that the rank of the finite field
regarded as an
-algebra has one of the two values 2n or 2n+1 ifn satisfies 1/2q+1<n<1/2(m(q)–2). Herem(q) denotes the maximum number of
-rational points of an algebraic curve of genus 2 over
. Using results of Davenport-Hasse, Honda and Rück we shall give lower bounds form(q) which are close to the Hasse-Weil bound
. For specialq we shall further show thatm(q) is equal to the Hasse-Weil bound. 相似文献
5.
M. A. Shepilov 《Cybernetics and Systems Analysis》1987,23(2):233-238
Conclusion The obvious deficiency of the method (1.3), (1.9) is the possible difficulty of the operation
. In connection with this one can note that all the above given statements remain valid if the number
is replaced by some positive lower bound of |f(t
k
,x)| on
.In computational methods, the presence of the Lipschitz constant is considered as a deficiency. In connection with this we can note that the Lipschitz constant L can be replaced by any of its upper estimates. For example, for a differentiable function f(z) one can take
.Translated from Kibernetika, No. 2, pp. 71–74, March–April, 1987. 相似文献
6.
Nader H. Bshouty Yishay Mansour Baruch Schieber Prasson Tiwari 《Computational Complexity》1992,2(3):244-255
Given an integerk, and anarbitrary integer greater than
, we prove a tight bound of
on the time required to compute
with operations {+, –, *, /, ·, }, and constants {0, 1}. In contrast, when the floor operation is not available this computation requires (k) time. Using the upper bound, we give an
time algorithm for computing log loga, for alln-bit integersa. This upper bound matches the lower bound for computing this function given by Mansour, Schieber, and Tiwari. To the best of our knowledge these are the first non-constant tight bounds for computations involving the floor operation. 相似文献
7.
Tomoyuki Yamakami 《Theory of Computing Systems》1992,25(3):177-201
This paper treates classes in the polynomial hierarchy of type two,
, that were first developed by Townsend as a natural extension of the Meyer-Stockmeyer polynomial hierarchy in complexity theory. For these classes, it is discussed whether each of them has the extension property and the three recursion-theoretic properties: separation, reduction, and pre-wellordering. This paper shows that every
0$$
" align="middle" border="0">
, lacks the pre-wellordering property by using a probabilistic argument on constant-depth Boolean circuits. From the assumption NP = coNP it follows by a pruning argument that
has the separation and extension properties. 相似文献
8.
9.
Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion
, where
is a compact set of matrices, is asymptotically stable if and only if
can be extended to a set
of nonnegative matrices B with
or
. Similar results are derived for differential inclusions. 相似文献
10.
Yu. N. Sotskov 《Cybernetics and Systems Analysis》1990,26(5):686-692
We consider the time-optimal scheduling problemn/m/J
of n jobs with fixed routes on m machines. The problem3/m/J/
with identical routes and the problem3/5/J/
are shown to be NP-hard. Similar results are obtained for the problem of minimizing the mean processing time of three jobs on m machines.Translated from Kibernetika, No. 5, pp. 50–54, September–October, 1990. 相似文献
11.
Summary Asynchronous two-dimensional iterative arrays of automata will be introduced where the underlying automata are not of Moore-type but of Mealy-type. We will prove that there exists a Mealy automaton,
, with only two states and one input and output for each of its four distinguished directions, such that any given Mealy-automaton can be realized by an iterative array with only
for its component-machines. It is known that loop-free nets cannot be as powerful as Mealy automata; however, we will show that any Mealy automaton can be realized by a network, N, with very restrictive component machines, where no signal may pass a loop in N. Using this fact asynchronous iterative arrays can be built up with one component machine,
such that any given Mealy automaton can be realized under the restriction that no signal passes a loop more than once.
contains only four states and one input and output for each direction. 相似文献
12.
Seth Breidbart 《Theory of Computing Systems》1978,12(1):129-131
We show that for any alphabet there is a setL
* such that ifC is any infinite co-infinite context-free language over , thenL
splitsC (i.e., each ofL
C,L
,
C, and
is infinite).Preparation of this paper was supported in part by the National Science Foundation under Grant No. MCS77-11360. 相似文献
13.
This paper studies the impact of order independence to the learnability of indexed families
of uniformly recursive languages from positive data. In particular, we considerset-driven andrearrangement-independent learners, i.e., learning devices whose output exclusively depends on the range and on the range and length of their input,
respectively. The impact of set-drivenness and rearrangement-independence on the behavior of learners to their learning power
is studied in dependence on thehypothesis space the learners may use. We distinguish betweenexact learnability (
has to be inferred with respect to
),class-preserving learning (
has to be inferred with respect to some suitably chosen enumeration of all the languages from
), andclass-comprising inference (
has to be learned with respect to some suitably chosen enumeration of uniformly recursive languages containing at least all
the languages from
).
Furthermore, we consider the influence of set-drivenness and rearrangement-independence for learning devices that realize
thesubset principle to different extents. Thereby we distinguish betweenstrong-monotonic, monotonic, andWeakmonotonic orconservative learning.
The results obtained are threefold. First, rearrangement-independent learning does not constitute a restriction except in
the case of monotonic learning. Next, we prove that for all but two of the learning models considered set-drivenness is a
severe restriction. However, class-comprising set-drivenconservative learning is exactly as powerful as unrestricted class-comprisingconservative learning. Finally, the power of class-comprising set-driven learning in the limit is characterized by equating the collection
of learnable indexed families with the collection of class-comprisingly conservatively inferable indexed families. These results
considerably extend previous work done in the field (see, e.g., [20] and [5]).
This is a substantially revised version of the authors' paper inProceedings of the 5th International Workshop on Algorithmic Learning Theory (ALT '94), Lecture Notes in Artificial Intelligence, Vol. 872, pp. 453–468, Springer-Verlag, Berlin. The first author has been partially
supported by the German Ministry for Research and Technology (BMFT) under Grant No. 01 IW 101. 相似文献
14.
We consider the solvability of the integral equation
for the unknown set W. A. bound of the integral
is given for some class of sets M. The results are applied in differential games.Translated from Kibernetika, No. 3, pp. 90–95, May–June 1990. 相似文献
15.
Terry Huntsberger 《Autonomous Robots》2001,11(3):341-346
Robotic missions beyond 2013 will likely be precursors to a manned habitat deployment on Mars. Such missions require robust control systems for long duration activities. Current single rover missions will evolve into deployment of multiple, heterogeneous cooperating robotic colonies. This paper describes the map-making memory and action selection mechanism of BISMARC (
iologically
nspired
ystem for
ap-based
utonomous
over
ontrol) that is currently under development at the Jet Propulsion Laboratory in Pasadena, CA (Huntsberger and Rose, Neutral Networks, 11(7/8):1497–1510). BISMARC is an integrated control system for long duration missions involving robots performing cooperative tasks. 相似文献
16.
Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems
In this paper, we investigate the problem of scheduling soft aperiodic requests in systems where periodic tasks are scheduled on a fixed-priority, preemptive basis. First, we show that given any queueing discipline for the aperiodic requests, no scheduling algorithm can minimize the response time of every aperiodic request and guarantee that the deadlines of the periodic tasks are met when the periodic tasks are scheduled on a fixed-priority, preemptive basis. We then develop two algorithms: Algorithm
is locally optimal in that it minimizes the response time of the aperiodic request at the head of the aperiodic service queue. Algorithm
is globally optimal in that it completes the current backlog of work in the aperiodic service queue as early as possible. 相似文献
17.
Otfried Schwarzkopf 《Algorithmica》1991,6(1):685-697
Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time
(n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple
(logn) algorithm for the distance transform with respect to theL
1-metric, an
(log2
n) algorithm for the transform with respect to theL
-metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL
k
-metric and takes time
(log3
n).This research was supported by the Deutsche Forschungsgemeinschaft under Grant Al 253/1-1, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen. 相似文献
18.
We consider the modified conjugate gradient procedure for solving A
=
in which the approximation space is based upon the Krylov space associated with A
1/p
and
, for any integer p. For the square-root MCG (p=2) we establish a sharpened bound for the error at each iteration via Chebyshev polynomials in
. We discuss the implications of the quickly accumulating effect of an error in
in the initial stage, and find an error bound even in the presence of such accumulating errors. Although this accumulation of errors may limit the usefulness of this method when
is unknown, it may still be successfully applied to a variety of small, almost-SPD problems, and can be used to jump-start the conjugate gradient method. Finally, we verify these theoretical results with numerical tests. 相似文献
19.
J. E. Hopcroft 《Theory of Computing Systems》1969,3(2):119-124
LetG andG
0 be context-free grammars. Necessary and sufficient conditions onG
0 are obtained for the decidability ofL(G
0)
L((G) It is also shown that it is undecidable for whichG
0,L(G)
is decidable. Furthermore, given thatL(G)
is decidable for a fixedG
0, there is no effective procedure to determine the algorithm which decidesL(G)
IfL(G
0) is a regular set,L(G) = L(G
0) is decidable if and only ifL(G
0) is bounded. However, there exist non-regular, unboundedL(G
0) for whichL(G) = L(G
0) is decidable. 相似文献
20.
We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule
, where
is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials
, we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For
and
, the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.
相似文献