Abstract
Let R be a rational language of (finite) words. We propose a way to decide whether Rw is equal to Fw for some finite set F. Next, in this case, we prove that one can compute the least integer, n, that can be the cardinal of some finite set F satisfying Rw=Fw. Furthermore one can construct all finite sets F satisfying both Rw=Fw and card (F)=n.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Boasson and M. Nivat, Adherences of languages; Journal of Computer and System Sciences, 20 (1980) 285–309.
J.R. Büchi, On decision method in restricted second-order arithmetics; Proc. Congr. Logic, Method. and Philos. Sci. (Stanford Univ. Press, Stanford, 1962) 1–11.
S. Eilenberg, Automata, Languages and Machines; Vol. A (Academic Press, New York, 1974).
L.H. Landweber, Decision problems for w-automata, Math. Syst. Theory 3 (1969) 376–384.
M. Latteux and E. Timmerman, Finitely generated w-languages; Information Processing Letters 23 (1986) 171–175.
I. Litovsky, Générateurs des langages rationnels de mots infinis; Thèse Univ. Lille I, 1988.
I. Litovsky and E. Timmerman, On generators of rational w-power languages; Theoretical Computer Science 53 (1987) 187–200.
R. MacNaughton, Testing and generating infinite sequences by a finite automaton; Information and Control 9 (1966) 521–530.
L. Staiger, A Note on Connected w-languages; EIK 16 (1980) 5/6, 245–251.
L. Staiger, Finite-state w-languages; Journal of Computer and System Sciences, 27 (1983) 434–448.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Litovsky, I. (1989). Rank of rational finitely generated W-languages. In: Csirik, J., Demetrovics, J., Gécseg, F. (eds) Fundamentals of Computation Theory. FCT 1989. Lecture Notes in Computer Science, vol 380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51498-8_30
Download citation
DOI: https://doi.org/10.1007/3-540-51498-8_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51498-5
Online ISBN: 978-3-540-48180-5
eBook Packages: Springer Book Archive