An algorithm to decide whether a rational subset of N^ k is recognizable

DOI10.1016/0304-3975(85)90059-3MaRDI QIDQ1070831zbMATH OpenOpenAlexFDO

Authors 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

formal power seriesfree monoidsunambiguous rational expression

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 440116
• A decision method for the recognizability of sets defined by number systems
• Algorithms for calculating the set of integers contained in a monoid finitely generated by positive rational numbers
• On \(\frac{p}{q}\)-recognisable sets
• An efficient algorithm to compute subsets of points in Z^n
• On recognizable sets of integers
• scientific article; zbMATH DE number 1839464
• Distinguishing subgroups of the rationals by their Ramsey properties
• Separability of rational relations in A^* N^m by recognizable relations is decidable
• An algorithm determining the set of lengths of polynomial cycles in Z_K^N

Cites work

• Bounded Regular Sets
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 3227138 (Why is no real title available?)
• scientific article; zbMATH DE number 3273002 (Why is no real title available?)
• Rational sets in commutative monoids

Cited in

(10)

• 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\}^*\)
• It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base
• Regularity conditions for iterated shuffle on commutative regular languages
• The commutative closure of shuffle languages over group languages is regular
• Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages
• Sparse and slender subsets of monoids.
• Regular languages and partial commutations
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
• Automata for the commutative closure of regular languages

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1070831)