Search results for "Formal languages"
showing 10 items of 322 documents
A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
Girod’s encoding method has been introduced in order to efficiently decode from both directions messages encoded by using finite prefix codes. In the present paper, we generalize this method to finite codes with a finite deciphering delay. In particular, we show that our decoding algorithm can be realized by a deterministic finite transducer. We also investigate some properties of the underlying unlabeled graph.
Some Decision Results on Nonrepetitive Words
1985
The paper addresses some generalizations of the Thue Problem such as: given a word u, does there exist an infinite nonrepetitive overlap free (or square free) word having u as a prefix? A solution to this as well as to related problems is given for the case of overlap free words on a binary alphabet.
"Table 6" of "Measurement of exclusive $\gamma\gamma\rightarrow \ell^+\ell^-$ production in proton-proton collisions at $\sqrt{s} = 7$ TeV with the A…
2015
Acoplanarity (ACO) distributions unfolded for detector resolution, and lepton pair trigger, reconstruction and identification efficiencies for mu+ mu- channel (empty bins are not reported).
Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited
2014
International audience; We present an extension of Eilenberg's variety theorem, a well-known result connecting algebra to formal languages. We prove that there is a bijective correspondence between formations of finite monoids and certain classes of languages, the formations of languages. Our result permits to treat classes of finite monoids which are not necessarily closed under taking submonoids, contrary to the original theory. We also prove a similar result for ordered monoids.; Nous présentons une extension du théorème des variétés d'Eilenberg, un résultat célèbre reliant l'algèbre à la théorie des langages formels. Nous montrons qu'il existe une correspondance bijective entre les form…
Local Gromov-Witten invariants are log invariants
2019
We prove a simple equivalence between the virtual count of rational curves in the total space of an anti-nef line bundle and the virtual count of rational curves maximally tangent to a smooth section of the dual line bundle. We conjecture a generalization to direct sums of line bundles.
Two-way automata with multiplicity
2005
We introduce the notion of two-way automata with multiplicity in a semiring. Our main result is the extension of Rabin, Scott and Shepherdson's Theorem to this more general case. We in fact show that it holds in the case of automata with multiplicity in a commutative semiring, provided that an additional condition is satisfied. We prove that this condition is also necessary in a particular case. An application is given to zig-zag codes using special two-way automata.
Formations of Monoids, Congruences, and Formal Languages
2015
The main goal in this paper is to use a dual equivalence in automata theory started in [25] and developed in [3] to prove a general version of the Eilenberg-type theorem presented in [4]. Our principal results confirm the existence of a bijective correspondence between three concepts; formations of monoids, formations of languages and formations of congruences. The result does not require finiteness on monoids, nor regularity on languages nor finite index conditions on congruences. We relate our work to other results in the field and we include applications to non-r-disjunctive languages, Reiterman s equational description of pseudovarieties and varieties of monoids.
A characterization of regular circular languages generated by marked splicing systems
2009
AbstractSplicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. A splicing system is defined by giving an initial set I and a set R of rules. Some unanswered questions are related to the computational power of circular splicing systems. In particular, a still open question is to find a characterization of circular languages generated by finite circular splicing systems (i.e., circular splicing systems with both I and R finite sets). In this paper we introduce a special class of the latter systems named marked systems. We prove that a marked system S generates a regular circular language if an…
Harnack and Shmul'yan pre-order relations for Hilbert space contractions
2015
We study the behavior of some classes of Hilbert space contractions with respect to Harnack and Shmul'yan pre-orders and the corresponding equivalence relations. We give some conditions under which the Harnack equivalence of two given contractions is equivalent to their Shmul'yan equivalence and to the existence of an arc joining the two contractions in the class of operator-valued contractive analytic functions on the unit disc. We apply some of these results to quasi-isometries and quasi-normal contractions, as well as to partial isometries for which we show that their Harnack and Shmul'yan parts coincide. We also discuss an extension, recently considered by S.~ter~Horst [\emph{J. Operato…
Congruence-based proofs of the recognizability theorems for free many-sorted algebras
2020
Abstract We generalize several recognizability theorems for free single-sorted algebras to free many-sorted algebras and provide, in a uniform way and without using either regular tree grammars or tree automata, purely algebraic proofs of them based on congruences.