Cônes rationnels commutatifs

DOI10.1016/0022-0000(79)90039-4zbMath0421.68074OpenAlexW2048244852MaRDI QIDQ1133330

Michel Latteux

Publication date: 1979

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(79)90039-4

zbMATH Keywords

conealgebraic languagesrational languagescommutative languagesrational transductionerasability

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The effect of end-markers on counter machines and commutativity, Rational languages and the Burnside problem, Algebraic languages and polyominoes enumeration, Literal shuffle, Representations of language families by homomorphic equality operations and generalized equality sets, On the usefulness of bifaithful rational cones, Semi-trace morphisms and rational transductions, The effect of jumping modes on various automata models, The commutative closure of a binary slip-language is context-free: A new proof., Unnamed Item, A result concerning the trios generated by commutative SLIP-languages, Refining the hierarchy of blind multicounter languages and twist-closed trios., On some transducer equivalence problems for families of languages, Semicommutations and algebraic languages, Enhancement of automata with jumping modes, Remarks about commutative context-free languages, On regularity of context-free languages, Every commutative quasirational language is regular, On some bounded semiAFLs and AFLs, Langages à un compteur, MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies, Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersections de langages algébriques bornes
• Syntactic operators on full semiAFLs
• Reversal-bounded multipushdown machines
• Familles de langages translatables et fermées par crochet
• Transductions des langages de Chomsky
• Bounded AFLs
• Some uniformly erasable families of languages
• Produit dans le cône rationnel engendre par D
• Langages algébriques, paires iterantes et transductions rationnelles
• Three theorems concerning principal AFLs
• A characterization of semilinear sets
• Sur diverses familles de langages fermées par transduction rationnelle
• The Unsolvability of the Recognition of Linear Context-Free Languages
• Une hiérarchie des parties rationnelles de N2