Non-prinicipalité du cylindre des langages à compteur

DOI10.1007/BF01768474zbMath0351.68026MaRDI QIDQ4121409

Jean-Michel Autebert

Publication date: 1977

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The hardest \(\operatorname{LL}(k)\) language ⋮ The hardest language for grammars with context operators ⋮ The Hardest LL(k) Language ⋮ On hardest languages for one-dimensional cellular automata ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Le cylindre des langages linéaires ⋮ The Hardest Language for Conjunctive Grammars ⋮ On characterisation of language families in terms of inverse morphisms ⋮ On hardest languages for one-dimensional cellular automata ⋮ Langages algébriques, paires iterantes et transductions rationnelles ⋮ Générateurs algébriques et systèmes de paires iterantes ⋮ Langages à un compteur ⋮ Remarks on multihead pushdown automata and multihead stack automata

Cites Work

• Unnamed Item
• Unnamed Item
• Two iteration theorems for some families of languages
• Transductions des langages de Chomsky
• Some uniformly erasable families of languages
• Sur diverses familles de langages fermées par transduction rationnelle
• The Hardest Context-Free Language
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• Counter machines and counter languages
• Studies in abstract families of languages
• Finite counting automata