References of "International Journal of Foundations of Computer Science"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

in International Journal of Foundations of Computer Science (2012), 23(5), 1035-1066

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related ... [more ▼]

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems. [less ▲]

Detailed reference viewed: 13 (7 ULg)
Full Text
Peer Reviewed
See detailLogical characterization of recognizable sets of polynomials over a finite field
Rigo, Michel ULg; Waxweiler, Laurent

in International Journal of Foundations of Computer Science (2011), 22(7), 1549-1563

The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination ... [more ▼]

The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P playing the role of the base of the numeration. Having in mind the theorem of Cobham from 1969 about recognizable sets of integers, it is natural to study $P$-recognizable sets of polynomials. Based on the results obtained in the Ph.D. thesis of the second author, we study the logical characterization of such sets and related properties like decidability of the corresponding first-order theory. [less ▲]

Detailed reference viewed: 85 (13 ULg)
Full Text
Peer Reviewed
See detailComputing Convex Hulls by Automata Iteration
Cantin, François ULg; Legay, Axel; Wolper, Pierre ULg

in International Journal of Foundations of Computer Science (2009), 20(4), 647-667

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors ... [more ▼]

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [less ▲]

Detailed reference viewed: 68 (23 ULg)