The search session has expired. Please query the service again.

Displaying 1541 – 1560 of 2186

Showing per page

Representations of a free group of rank two by time-varying Mealy automata

Adam Woryna (2005)

Discussiones Mathematicae - General Algebra and Applications

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.

Réseaux modulaires à structure variable

Louise Martin (1981)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

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.

Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

Beate Bollig (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Beate Bollig (2010)

RAIRO - Theoretical Informatics and Applications

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...

Returning and non-returning parallel communicating finite automata are equivalent

Ashish Choudhary, Kamala Krithivasan, Victor Mitrana (2007)

RAIRO - Theoretical Informatics and Applications

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.

Rewriting on cyclic structures: Equivalence between the operational and the categorical description

Andrea Corradini, Fabio Gadducci (2010)

RAIRO - Theoretical Informatics and Applications

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...

Robust optimality of Gaussian noise stability

Elchanan Mossel, Joe Neeman (2015)

Journal of the European Mathematical Society

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...

Root clustering of words

Gerhard Lischke (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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