An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable

DOI10.1016/0304-3975(85)90059-3zbMath0585.68072OpenAlexW1964508684MaRDI QIDQ1070831

Philippe Gohon

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90059-3

zbMATH Keywords

free monoidsformal power seriesunambiguous rational expression

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (8)

Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages ⋮ Regular languages and partial commutations ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability ⋮ Decidability of the star problem in \(A^*\times{}\{ b\}^*\) ⋮ Sparse and slender subsets of monoids. ⋮ Regularity conditions for iterated shuffle on commutative regular languages ⋮ The commutative closure of shuffle languages over group languages is regular

Cites Work

• Rational sets in commutative monoids
• Bounded Regular Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable