On cancellation properties of languages which are supports of rational power series

DOI10.1016/0022-0000(84)90026-6zbMath0578.68061OpenAlexW2008570649MaRDI QIDQ1066677

Christophe Reutenauer, Antonio Restivo

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90026-6

zbMATH Keywords

regular languagemorphismsfree monoidEhrenfeucht conjecturenoncommutative power seriesfinite test set

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Valuations, completions, formal power series and related constructions (associative rings and algebras) (16W60) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (9)

Rational languages and the Burnside problem ⋮ A note on the equivalence problem of rational formal power series ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Rational and Recognisable Power Series ⋮ On some transducer equivalence problems for families of languages ⋮ Generalized cancellation-and-permutation properties, regular languages and supports of rational series ⋮ Rational series with coefficients in a commutative ring ⋮ On some variants of the Ehrenfeucht conjecture ⋮ Weighted automata

Cites Work

• On binary equality sets and a solution to the test set conjecture in the binary case
• An Ogden-like iteration lemma for rational power series
• Un théorème de factorisation des produits d'endomorphismes de \(K^N\)
• Test sets and checking words for homomorphism equivalence
• On some questions of rationality and decidability
• A note on recurring series
• On the definition of a family of automata
• Sur les éléments inversibles de l'algèbre de Hadamard des séries rationnelles
• Test sets for context free languages and algebraic systems of equations over a free monoid
• Pumping Lemmas for Regular Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On cancellation properties of languages which are supports of rational power series