Decidability questions related to abstract numeration systems

DOI10.1016/j.disc.2004.05.004zbMath1076.68040OpenAlexW2037985830MaRDI QIDQ1877679

Michel Rigo, Juha Honkala

Publication date: 19 August 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.05.004

zbMATH Keywords

Numeration systemDecidabilityHD0L system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability (number-theoretic aspects) (11U05)

Related Items

A Hierarchy of Automaticω-Words having a Decidable MSO Theory ⋮ Periodicity of morphic words ⋮ A DECISION PROBLEM FOR ULTIMATELY PERIODIC SETS IN NONSTANDARD NUMERATION SYSTEMS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logic and \(p\)-recognizable sets of integers
• Numeration systems, linear recurrences, and regular sets
• Bertrand numeration systems and recognizability
• Generalization of automatic sequences for numeration systems on a regular language
• It is decidable whether the image of an \(\mathbb N\)-rational sequence has a base
• Thin and slender languages
• On the Images of ℕ-Rational Sequences Counting Multiplicities
• A decision method for the recognizability of sets defined by number systems
• Automatic Sequences
• Uniform tag sequences
• Numeration systems on a regular language
• Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series