Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable

DOI10.1016/j.ipl.2005.09.018zbMath1184.68310OpenAlexW1974449814MaRDI QIDQ845664

Serge Grigorieff, Christian Choffrut

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.09.018

zbMATH Keywords

automataseparabilityformal languagesrecognizability

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Preface ⋮ On the separability of sparse context-free languages and of bounded rational relations

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modelization of deterministic rational relations
• Semigroups, Presburger formulas, and languages
• Multitape one-way nonwriting automata
• Rational sets in commutative monoids
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• On Relations Defined by Generalized Finite Automata
• Bounded Algol-Like Languages

This page was built for publication: Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable