Search results for "Formal language"
showing 10 items of 357 documents
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.
Words with the Maximum Number of Abelian Squares
2015
An abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain \(\varTheta (n^2)\) distinct factors that are abelian squares. We study infinite words such that the number of abelian square factors of length n grows quadratically with n.
Quantum Finite State Transducers
2000
We introduce quantum finite state transducers (qfst), and study the class of relations which they compute. It turns out that they share many features with probabilistic finite state transducers, especially regarding undecidability of emptiness (at least for low probability of success). However, like their `little brothers', the quantum finite automata, the power of qfst is incomparable to that of their probabilistic counterpart. This we show by discussing a number of characteristic examples.
On the class of languages recognizable by 1-way quantum finite automata
2000
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.