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 (22)

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

This page was built for publication: Cônes rationnels commutatifs