×

zbMATH — the first resource for mathematics

Representation of rational functions with prefix and suffix codings. (English) Zbl 0823.68055
Summary: We proceed with the characterization of rational functions by means of restricted class of morphisms. Left subsequential transductions can be factored in an endmarking followed by an uniform morphism, the inverse of a prefix morphism and an alphabetic morphism. Rational functions require the inverse of a prefix morphism followed by the inverse of a suffix morphism.
MSC:
68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Keywords:
suffix morphism
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnold, A.; Latteux, M., A new proof of two theorems about rational transductions, Theoret. comput. sci., 8, 261-263, (1979) · Zbl 0401.68057
[2] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[3] Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press New York · Zbl 1022.94506
[4] Eilenberg, S., Automata, languages and machines, Vol A, (1974), Academic Press New York · Zbl 0317.94045
[5] Elgot, C.C.; Mezei, J.E., On relations defined by generalized finite automata, IBM J. res. develop., 9, 47-68, (1965) · Zbl 0135.00704
[6] Harju, T.; Kleijn, H.C.M., Decidability problems for unary output sequential transducers, Discrete appl. math., 32, 131-140, (1991) · Zbl 0743.68098
[7] Harju, T.; Kleijn, H.C.M.; Latteux, M., Compositional representation of rational functions, RAIRO théor. inform appl., 26, 243-255, (1992) · Zbl 0769.68097
[8] Harju, T.; Kleijn, H.C.M.; Latteux, M., Deterministic rational functions, Acta inform., 29, 545-554, (1992) · Zbl 0790.68036
[9] Karhumäki, J.; Linna, M., A note on morphic characterization of languages, Discrete appl. math., 5, 243-246, (1983) · Zbl 0499.68031
[10] Latteux, M.; Leguy, J., On the composition of morphisms and inverse morphisms, (), 420-432 · Zbl 0523.68067
[11] Latteux, M.; Timmerman, E., Bifaithful starry transductions, Inform. process. lett., 28, 1-4, (1988) · Zbl 0666.68072
[12] Latteux, M.; Turakainen, P., A new normal form for the composition of morphisms and inverse morphisms, Math. systems theory, 20, 261-271, (1987) · Zbl 0638.68087
[13] Nivat, M., Transductions des langages de chomsky, Ann. inst. Fourier, 18, 339-456, (1968) · Zbl 0313.68065
[14] Schützenberger, M.P., Sur LES relations rationnelles entre monoïdes libres, Theoret. comput. sci., 3, 243-259, (1976) · Zbl 0358.68129
[15] Turakainen, P., A homomorphic characterization of principal semi-AFLs without using intersection with regular sets, Inform. sci., 27, 141-149, (1982) · Zbl 0506.68063
[16] Turakainen, P., A machine-oriented approach to composition of morphisms and inverse morphisms, EATCS bull., 20, 162-166, (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.