ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
Filter
  • Articles  (2,863)
  • Springer  (2,863)
  • 1980-1984  (2,863)
  • 1945-1949
  • Computer Science  (2,863)
Collection
  • Articles  (2,863)
Years
Year
Journal
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 16 (1983), S. 57-60 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract It is shown that a Thue system of the formT 1 = {(w,e)} is Church-Rosser if and only if there is a Thue systemT 2 that is Church-Rosser and is equivalent toT 1.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 16 (1983), S. 133-157 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We associate to a maximal codeX on an alphabetA a dynamical system Ω; our main result proves that the property of unique decipherability implies that the partition of Ω associated to the letters ofA is a Bernoulli partition. Surprisingly it is possible to give two very different proofs of this result: the first one uses probability measures on monoids together with methods from automata theory; the other is based on results of entropy theory.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 16 (1983), S. 233-249 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In contrast to the case of a single dynamical system, the asymptotic stability of orbits of control systems cannot be characterized in terms of suitably defined Lyapunov functions. It is shown that the existence of Lyapunov functions corresponds to a stronger type of asymptotic stability, which is defined by introducing higher prolongations.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 16 (1983), S. 191-231 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Several equivalence decision algorithms for classes of grammars, program schemes, transducers follow the general pattern of the Korenjak-Hopcroft algorithm for deciding the equivalence of simple deterministic grammars. An axiomatic framework is presented which points out the essence of the Korenjak-Hopcroft algorithm and applies to numerous situations.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 16 (1983), S. 159-183 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Call a connected planar graphG legal if it has at least two nodes, no parallel edges or self-loops and at most two terminals (degree 1 nodes) and all terminals and degree 2 nodes are exterior. This class of graphs arose in connection with a two-dimensional generating system for modeling growth by binary cell division. Showing that any permitted pattern can be generated properly requires a matching or pairing lemma. The vertex set of a legal graph withn nodes can be split intop adjacent pairs ands singletons withs p, resulting in a matching which includes at least $$2\left[ {\frac{n}{3}} \right]$$ nodes. This bound is sharp in the sense that there are legal graphs for which this matching is maximum. The matching can be implemented by a linear time algorithm. A legal graph witht terminals and n≥4 nodes has a spanning tree with at most $$\left[ {\frac{{n - t}}{2}} \right] + t$$ terminals; this bound is sharp. Such a spanning tree can be constructed by an algorithm which operates in almost linear time.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 16 (1983), S. 185-188 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The class of readout maps of the early state space literature and the class of operators which are both causal and anticausal are compared. The first class is a subset of the second and is shown by example to be a proper subset. A characterization of the smaller class in terms of causality structure is presented. We denote this characterization by the term completely memoryless.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 17 (1984), S. 85-96 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A simple problem concerning evaluation of programs is shown to be nonelementary recursive. The problem is the following: Given an input-free programP (i.e. all variables are initially 0) without nested loops using only instructions of the formx ← 1, x ← x + y, $$x \leftarrow x\dot - y$$ ,do x... end, doesP output 0? This problem has time complexity $$2^{2^{ {\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern2mu \raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}} ^2 } } $$ }cn-levels for some constantc. Other results are presented which show how the complexity of the 0-evaluation problem changes when the nonlooping instructions are varied. For example, it is shown that 0-evaluation is PSPACE-complete even for the case when the nonlooping instructions are onlyx ← x + 1,if x = 0then y ←y $$y \leftarrow y\dot - 1$$ .
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 17 (1984), S. 29-45 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The main result of this paper is a separation result: there is a positive integerk such that for all well-behaving functionst(n), there is a language accepted by a nondeterministic (multi-tape) Turing machine in timet(n) which cannot be accepting by any deterministic (multitape) Turing machine in timeO(t(n)) and simultaneously spaceo((t(n)) 1/k ). This implies, for example that for any positive integer,l,l ≠k, there is a language accepted by an l time bounded NDTM which cannot be accepted by a DTM in time and spaceO(n l ) andO((logn) l ′) respectively for anyl′. Such a result is not provable by direct diagonalization because we do not have time to “simulate and do the opposite". We devise a different method for accomplishing the result: We first use an alternating Turing machine to speed up the simulation of a time and space bounded DTM and then argue that if our separation result did not hold, every NDTM can itself be simulated faster by another NDTM producing a contradiction to the standard hierarchy results. Some other applications of this method are also presented.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 9
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we consider the problem of uniform asymptotic stabilization of neutral delay differential systems by a suitable choice of linear feedback law, where the controller is static and at timet 0 has full knowledge ofx(t 0) ∈ ℝ n as well asx(t 0 − d) for finitely many delays present in the system. Using complex analysis in several variables in a Banach algebra context we present a solution to this problem in the form of a sufficient condition for the existence of such a stabilizing feedback gain. This condition is a weak form of (algebraic) reachability together with a condition, which we call resolvability, on the solution of an associated algebraic Riccati equation. In the case of commensurable delays our results apply to neutral systems having aD-operator which is stable in the sense of Cruz and Hale. In the non-commensurate case, our results hold for systems with aD-operator satisfying a stronger condition on the spectrum of the evolution equation, which we call formal stability. A graphical criterion, in the spirit of the multi-dimensional Nyquist theory, is presented for formal stability ofD. We find these results especially interesting in light of recent work [39] which shows that, for a special class of systems, formal stability is necessary for stabilization by a feedback gain of the type considered here. This, in fact, gives a counterexample [39] to the well known condition of Pandolfi [40]. Included among our results is an extension to the neutral case of the result in [11] which states that if the pointwise Kronecker indices are constant then the system is feedback equivalent to a delay-free system. As corollaries to this result we obtain some existing results [33] on canonical forms for time-delay systems, and, in addition, exhibit a large class of systems which are resolvable.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Theory of computing systems 17 (1984), S. 159-166 
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Sufficient conditions that a two-dimensional system with output is locally observable are presented. Known results depend on time derivatives of the output and the inverse function theorem. In some cases, no information is provided by these theories, and one must study observability by other methods. We dualize the observability problem to the controllability problem, and apply the deep results of Hermes on local controllability to prove a theorem concerning local observability.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...