Epsilon weak precedence grammars and languages
Equality sets for recursively enumerable languages
We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter , where deletes the letters not in . Then we deduce...
Equality sets for recursively enumerable languages
We consider shifted equality sets of the form EG(a,g1,g2) = {ω | g1(ω) = ag2(ω)}, where g1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and (EG(J)) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L ⊆ A* is a projection of a shifted equality set, that is, L = πA(EG(a,g1,g2)) for some (nonerasing) morphisms g1...
Equations and dot-depth one.
Equations associated with a context-free grammar
Equations on the semidirect product of a finite semilattice by a -trivial monoid of height
Erasing automata recognize more than context-free languages
Étude spectrale de la multiplication -adique
Every commutative quasirational language is regular
Expletives in languages and middle units in semigroups.
Extending regular expressions with homomorphic replacement
We define H- and EH-expressions as extensions of regular expressions by adding homomorphic and iterated homomorphic replacement as new operations, resp. The definition is analogous to the extension given by Gruska in order to characterize context-free languages. We compare the families of languages obtained by these extensions with the families of regular, linear context-free, context-free, and EDT0L languages. Moreover, relations to language families based on patterns, multi-patterns,...
Factorisation des ensembles préfixiels
Factors of generalized Rudin-Shapiro sequences. (Facteurs des suites de Rudin-Shapiro généralisées.)
Fair expressions and regular languages over lists
Fairness and regularity for SCCS processes
Familles de langages
Fermeture de certaines classes de langages formels sous des permutations linguistiques
Finitary codes for biinfinite words
Finite automata and algebraic extensions of function fields
We give an automata-theoretic description of the algebraic closure of the rational function field over a finite field , generalizing a result of Christol. The description occurs within the Hahn-Mal’cev-Neumann field of “generalized power series” over . In passing, we obtain a characterization of well-ordered sets of rational numbers whose base expansions are generated by a finite automaton, and exhibit some techniques for computing in the algebraic closure; these include an adaptation to positive...
Finite automata and arithmetic.