The search session has expired. Please query the service again.
Displaying 1541 –
1560 of
2186
In the group theory various representations of free groups are used. A representation of a free group of rank two by the so-calledtime-varying Mealy automata over the changing alphabet is given. Two different constructions of such automata are presented.
Si dà una formalizzazione dei moduli e delle reti modulari a struttura variabile. Si dimostra che per ogni automa finito a struttura variabile esiste una rete modulare a struttura variabile che lo simula. Si stabilisce il legame tra un automa a struttura variabile e l'automa a struttura variabile associato a una rete modulare a struttura variabile che lo simula.
Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential...
Branching programs are a well established computation model for
Boolean functions, especially read-once branching programs have
been studied intensively.
In this paper the expressive power of nondeterministic read-once branching
programs, more precisely the class of functions
representable in polynomial size, is investigated.
For that reason two restricted models of nondeterministic read-once
branching programs are defined and a lower bound method is presented.
Furthermore, the first exponential...
A parallel communicating automata system consists of several automata working independently in parallel and
communicating with each other by request with the aim of recognizing a word.
Rather surprisingly, returning parallel communicating finite automata systems are equivalent
to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata.
Some open problems are finally formulated.
We present a categorical formulation
of the rewriting of possibly cyclic term graphs, based on a
variation of algebraic 2-theories. We show that
this presentation is equivalent to the well-accepted
operational definition proposed by Barendregt et al. – but
for the
case of circular redexes , for which we propose (and
justify formally) a different treatment.
The categorical framework allows us to model in a concise way
also automatic garbage collection
and rules
for sharing/unsharing and...
We prove that under the Gaussian measure, half-spaces are uniquely the most noise stable sets. We also prove a quantitative version of uniqueness, showing that a set which is almost optimally noise stable must be close to a half-space. This extends a theorem of Borell, who proved the same result but without uniqueness, and it also answers a question of Ledoux, who asked whether it was possible to prove Borell’s theorem using a direct semigroup argument. Our quantitative uniqueness result has various...
Six kinds of both of primitivity and periodicity of words, introduced by Ito and Lischke [M. Ito and G. Lischke, Math. Log. Quart. 53 (2007) 91–106; Corrigendum in Math. Log. Quart. 53 (2007) 642–643], give rise to defining six kinds of roots of a nonempty word. For 1 ≤ k ≤ 6, a k-root word is a word which has exactly k different roots, and a k-cluster is a set of k-root words u where the roots of u fulfil a given prefix relationship. We show that out of the 89 different clusters that can be considered...
Currently displaying 1541 –
1560 of
2186