References of "Rampersad, Narad"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailMulti-dimensional sets recognizable in all abstract numeration systems
Charlier, Emilie ULg; Lacroix, Anne ULg; Rampersad, Narad ULg

in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications (2012), 46(1), 51-65

We prove that the subsets of N^d that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional ... [more ▼]

We prove that the subsets of N^d that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting. [less ▲]

Detailed reference viewed: 70 (22 ULg)
Full Text
Peer Reviewed
See detailThe minimal automaton recognizing mN in a linear numeration system
Charlier, Emilie ULg; Rampersad, Narad ULg; Rigo, Michel ULg et al

in Integers: Electronic Journal of Combinatorial Number Theory (2011), 11B(A4), 1-24

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼]

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>1 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]

Detailed reference viewed: 75 (30 ULg)
Full Text
Peer Reviewed
See detailInverse star, borders, and palstars
Rampersad, Narad ULg; Shallit, Jeffrey; Wang, Ming-wei

in Information Processing Letters (2011), 111

A language L is closed if L = L*. We consider an operation on closed languages, L-*, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L-* is also regular. We show ... [more ▼]

A language L is closed if L = L*. We consider an operation on closed languages, L-*, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L-* is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free. [less ▲]

Detailed reference viewed: 8 (0 ULg)
Full Text
Peer Reviewed
See detailAbelian primitive words
Domaratzki, Michael; Rampersad, Narad ULg

in Mauri, Giancarlo; Leporati, Alberto (Eds.) DLT 2011 - Developments in Language Theory (2011)

We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine ... [more ▼]

We investigate Abelian primitive words, which are words that are not Abelian powers. We show that unlike classical primitive words, the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time. Also different from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration problems and the relation to the theory of codes. [less ▲]

Detailed reference viewed: 6 (0 ULg)
Full Text
Peer Reviewed
See detailState complexity of testing divisibility
Charlier, Emilie ULg; Rampersad, Narad ULg; Rigo, Michel ULg et al

in McQuillan, Ian, Pighizzini, Giovanni (Ed.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (2010, August)

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an ... [more ▼]

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]

Detailed reference viewed: 60 (19 ULg)
Full Text
Peer Reviewed
See detailStructure of the minimal automaton of a numeration language
Charlier, Emilie ULg; Rampersad, Narad ULg; Rigo, Michel ULg et al

in Actes de LaCIM 2010 (2010, August)

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼]

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. [less ▲]

Detailed reference viewed: 63 (19 ULg)
Full Text
Peer Reviewed
See detailStructure of the minimal automaton of a numeration language and applications to state complexity
Charlier, Emilie ULg; Rampersad, Narad ULg; Rigo, Michel ULg et al

in Actes des Journées Montoises d'Informatique Théorique (2010)

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼]

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root > 1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number . Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]

Detailed reference viewed: 32 (7 ULg)