Results 31 to 40 of about 1,048 (100)
The polynomial-time hierarchy [PDF]
, 1976 The polynomial-time hierarchy is that subrecursive analog of the Kleene arithmetical hierarchy in which deterministic (nondeterministic) polynomial time plays the role of recursive (recursively enumerable) time.
Stockmeyer, Larry J.
core +1 more source
On the Complexity of the Word Problem for Automaton Semigroups and Automaton Groups
, 2017 In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are ...
D'Angeli, Daniele +2 more
core +1 more source
State-by-state calculations for all channels of the exotic $(\mu^-,e^-)$ conversion process [PDF]
, 1997 The coherent and incoherent channels of the neutrinoless muon to electron conversion in nuclei, $\mu^- (A,Z) \to e^- (A,Z)^*$, are studied throughout the periodic table.
Faessler, Amand +3 more
core +2 more sources
Upper and lower bounds for first order expressibility [PDF]
, 1982 We study first order expressibility as a measure of complexity. We introduce the new class Var&Sz[v(n),z(n)] of languages expressible by a uniform sequence of sentences with v(n) variables and size O[z(n)].
Immerman, Neil
core +1 more source
Linear Bounded Composition of Tree-Walking Tree Transducers: Linear Size Increase and Complexity [PDF]
, 2019 Compositions of tree-walking tree transducers form a hierarchy with respect to the number of transducers in the composition. As main technical result it is proved that any such composition can be realized as a linear bounded composition, which means that
Engelfriet, Joost +2 more
core +2 more sources
Translational lemmas, polynomial time, and (log n)j-space [PDF]
, 1976 Translational lemmas are stated in a general framework and then applied to specific complexity classes. Necessary and sufficient conditions are given for every set accepted by a Turing acceptor which operates in linear or polynomial time to be accepted ...
Book, Ronald V.
core +1 more source
The Gauss map of immersions of Riemannian manifolds in spaces of constant curvature
, 1968 With an immersion x of a Riemannian n-manifold M into a Euclidean Nspace E there is associated the Gauss map, which assigns to a point p of M the n-plane through the origin of E and parallel to the tangent plane of x(M) at x(p), and is a map of M into ...
M. Obata
semanticscholar +1 more source
Global Versus Local Computations: Fast Computing with Identifiers
, 2017 This paper studies what can be computed by using probabilistic local interactions with agents with a very restricted power in polylogarithmic parallel time.
A Schönhage +16 more
core +1 more source
Mediated population protocols [PDF]
, 2009 We extend here the Population Protocol (PP) model of Angluin et al. (2004, 2006) [2,4] in order to model more powerful networks of resource-limited agents that are possibly mobile.
Chatzigiannakis, Ioannis +2 more
core +2 more sources
Logspace self-reducibility [PDF]
, 1988 A definition of self-reducibility is proposed to deal with logarithmic space complexity classes. A general property derived from the definition is used to prove known results comparing uniform and nonuniform complexity classes below polynomial time, and ...
Balcázar Navarro, José Luis
core +1 more source