Recursivite et cônes rationnels fermés par intersection

DOI10.1007/BF02576519zbMath0421.68075OpenAlexW2086340783MaRDI QIDQ1133331

André Arnold, Michel Latteux

Publication date: 1978

Published in: Calcolo (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02576519

zbMATH Keywords

decidabilityrecursive languagesrational conesabstract families of languagesquasi-commutative grammarsreachability problem in vector-addition systemssemi-Dyck language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40)

Related Items

Well-structured transition systems everywhere!, The ideal view on Rackoff's coverability technique, Forward analysis for WSTS, part I: completions, The Parametric Complexity of Lossy Counter Machines

Cites Work

• Unnamed Item
• Unnamed Item
• Reversal-bounded multipushdown machines
• Transductions des langages de Chomsky
• Some decision problems related to the reachability problem for Petri nets
• Commutative grammars
• Parallel program schemata
• What makes some language theory problems undecidable
• Petri nets and szilard languages
• Une hiérarchie des parties rationnelles de N2
• Intersection-closed full AFL and the recursively enumerable languages