ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
Collection
Publisher
Years
• 1
Electronic Resource
Springer
Theory of computing systems 16 (1983), S. 1-8
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract In this note we propose VLSI layouts for the cube-connectedcycles (CCC) in a three-dimensional medium. The first type of layout is for the all-active-volume mode, where computing modules are placed anywhere within the solid chip; the second type is for the one-active-layer mode, where computing modules are placed on an external face of the solid chip. In both cases we present volume × time optimal realizations. In addition, by opening the cycles of the CCC, one obtains the well-known FFT network. Both realizations use minimum volume; an all-active-volume realization with the same volume performance was earlier proposed by Rosenberg, while the present one-active-layer realization is the only optimal one that is known.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 2
Electronic Resource
Springer
Theory of computing systems 12 (1978), S. 325-346
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract LetM be anm-by-n matrix with entries in {0,1,⋯,K}. LetC(M) denote the minimum possible number of edges in a directed graph in which (1) there arem distinguished vertices calledinputs, andn other distinguished vertices calledoutputs; (2) there is no directed path from an input to another input, from an output to another output, or from an output to an input; and (3) for all 1 ≤i ≤m and 1 ≤j ≤n, the number of directed paths from thei-th input to thej-th output is equal to the (i,j)-th entry ofM. LetC(m,n,K) denote the maximum ofC(M) over allm-by-n matricesM with entries in {0,1,⋯,K}. We assume (without loss of generality) thatm ≥n, and show that ifm=(K+1) 0(n) andK=22 0(m) , thenC(m,n,K)= H/logH + 0(H/logH), whereH=mnlog(K + 1) and all logarithms have base 2. The proof involves an interesting problem of Diophantine approximation, which is solved by means of an unusual continued fraction expansion.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 3
Electronic Resource
Springer
Theory of computing systems 12 (1978), S. 297-324
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract A grammar formF defines via a so-calledinterpretation mechanism, a family of languages (F). In this paper we establish that for many grammar formsF, (the family of context-free languages) implies (F)= RE (the family of recursively enumerable sets). We conjecture that this is also true in general. Because of this, it seems necessary to use restricted interpretations for non context-free grammar forms, a form giving then rise to a family We compare the obvious alternatives for restricting interpretations and focus attention on two promising alternatives, Q (F) and st(F) and their combination Q, st(F). Using st-interpretations, surprising families can be generated and strong normal form results can be obtained. Closure results and decidability results are also given. UnderQ, st-interpretation, it is possible to characterize a number of well-known families of languages between CF and RE, including the families of EOL, ETOL, matrix and scattered context languages.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 4
Electronic Resource
Springer
Theory of computing systems 12 (1978), S. 347-359
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract It is shown that every stochastic automaton generates a semigroup of continuous linear operators in order to give conditions for the convergence of certain operators connected with infinite input sequences. The main results of this note are conditions for the infinitesimal stability of stochastic automata. Since under suitable conditions the behaviour of a learning system can be represented by a stochastic automaton, these results apply to the asymptotic stability of learning.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 5
Electronic Resource
Springer
Theory of computing systems 12 (1978), S. 361-370
ISSN: 1433-0490
Keywords: Nonlinear systems ; controllability ; reachable set ; vector bundle
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract Consider the nonlinear system $$\dot x(t) = f(x(t)) + \sum\limits_{i = 1}^m {u_i (t)g_i (x(t)), x(0) = x_0 \in M}$$ whereM is aC ∞ realn-dimensional manifold,f, g 1,⋯.,g m areC ∞ vector fields onM, andu 1 ,..,u m are real-valued controls. Ifm=n−1 andf, g 1 ,⋯,g m are linearly independent, then the system is called a hypersurface system, and necessary and sufficient conditions for controllability are known. For a generalm, 1 ≤m ≤n−1, and arbitraryC ∞ vector fields,f, g 1 ,⋯,g m , assume that the Lie algebra generated byf, g 1 ,⋯,g m and by taking successive Lie brackets of these vector fields is a vector bundle with constant fiber (vector space) dimensionp onM. By Chow's Theorem there exists a maximalC ∞ realp-dimensional submanifoldS ofM containingx 0 with the generated bundle as its tangent bundle. It is known that the reachable set fromx 0 must contain an open set inS. The largest open subsetU ofS which is reachable fromx 0 is called the region of reachability fromx 0. IfO is an open subset ofS which is reachable fromx 0,S we find necessary conditions and sufficient conditions on the boundary ofO inS so thatO = U. Best results are obtained when it is assumed that the Lie algebra generated byg 1,⋯,g m and their Lie brackets is a vector bundle onM.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 6
Electronic Resource
Springer
Theory of computing systems 12 (1978), S. 371-393
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract A universal input is an inputu with the property that, whenever two states give rise to a different output for some input, then they give rise to a different output foru. For an observable system,u is universal if the initial state can be reconstructed from the knowledge of the output foru. It is shown that, for continuous-time analytic systems, analytic universal inputs exist, and that, in the class ofC ∞ inputs, universality is a generic property. Stronger results are proved for polynomial systems.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 7
Electronic Resource
Springer
Theory of computing systems 13 (1979), S. 81-93
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract Indecomposable local maps of one-dimensional tessellation automata are studied. The main results of this paper are the following. (1) For any alphabet ∑ containing two or more symbols and for anyn≥ 1, there exist indecomposable scope-n local maps over ∑. (2) If ∑ is a finite field of prime order, then a linear scope-n local map over ∑ is indecomposable if and only if its associated polynomial is an irreducible polynomial of degreen − 1 over ∑, except for a trivial case. (3) Result (2) is no longer true if ∑ is a finite field whose order is not prime.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 8
Electronic Resource
Springer
Theory of computing systems 13 (1979), S. 29-43
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract We determine the computational complexity of membership, emptiness and infiniteness for several types ofL systems. TheL systems we consider are ED0L, E0L, EDT0L, and ET0L, with and without empty productions. For each problem and each type of system we establish both upper and lower bounds on the time or memory required for solution by Turing machines.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 9
Electronic Resource
Springer
Theory of computing systems 13 (1979), S. 1-27
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract This paper presents a formulation, within the framework of initial algebra semantics, of Knuthian semantic systems (K-systems) which contain both synthesized and inherited attributes. The approach is based on viewing the semantics of a derivation tree of a context-free grammar as a set of values, called an attribute valuation, assigned to the attributes of all its nodes. Any tree's attribute valuation which is consistent with the semantic rules of the K-system may be chosen as the semantics of that derivation tree. The set of attribute valuations of a given tree is organized as a complete partially ordered set such that the semantic rules define a continuous transformation on this set. The least fixpoint of this transformation is chosen as the semantics of a given derivation tree. The mapping from derivation trees to their least fixpoint semantics is a homomorphism between certain algebras. Thus, the semantics of a K-system is an application of the Initial Algebra Semantics Principle of Goguen and Thatcher. This formulation permits a precise definition of K-systems, and generalizes Knuth's original formulation by defining the meaning of recursive (circular) semantic specifications. The algebraic formulation of K-systems is applied to proving the equivalence of K-systems having the same underlying grammar. Such proofs may require verifying that a K-system possesses certain properties and to this end, a principle of structural induction on many-sorted algebras is formulated, justified, and applied.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
• 10
Electronic Resource
Springer
Theory of computing systems 13 (1979), S. 45-53
ISSN: 1433-0490
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract For each fixed set of Boolean connectives, how hard is it to determine satisfiability for formulas with only those connectives? We show that a condition sufficient for NP-completeness is that the functionx Λ ~ y be representable, and that any set of connectives not capable of representing this function has a polynomial-time satisfiability problem.
Type of Medium: Electronic Resource
Location Call Number Expected Availability
Others were also interested in ...
Close ⊗