Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427261 | Information Processing Letters | 2015 | 5 Pages |
Abstract
•We provide upper and lower bounds for Simon's index for piecewise testability.•This index depends on the length of considered subwords and the alphabet size.•The previously known bounds focused on fixed length of subwords.•Our bounds are relevant when alphabet size is fixed and length of subwords vary.•They give a growth rate that is exponential and not doubly exponential.
Simon's congruence, denoted by ∼n∼n, relates words having the same subwords of length up to n. We show that, over a k -letter alphabet, the number of words modulo ∼n∼n is in 2Θ(nk−1logn)2Θ(nk−1logn).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
P. Karandikar, M. Kufleitner, Ph. Schnoebelen,