Partial commutations and faithful rational transductions. (English) Zbl 0548.68073

Summary: We study the operation of partial commutation in connection with other operations such as partitioned commutation, twin shuffle, intersection and faithful rational transductions. From that study we get a very simple characterization for the following families of languages: MULTI-RESET, BNP and Q the family of quasirealtime languages.


68Q45 Formal languages and automata
Full Text: DOI


[1] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[2] Bertoni, A.; Mauri, G.; Sabadini, N., A hierarchy of regular trace languages and some combinatorial applications, 2nd world conf. on mathematics at the service of men, (1982), Las Palmas · Zbl 0512.68056
[3] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular trace languages, (), 61-71 · Zbl 0486.68079
[4] Boasson, L.; Nivat, M., Sur diverses familles de langages fermées par transduction rationnelle, Acta informatica, 2, 180-188, (1973) · Zbl 0242.68037
[5] Book, R., Intersections of CFL’s and related structures, (), 184-192
[6] Book, R.; Greibach, S., Quasi-realtime languages, Math. systems theory, 4, 97-111, (1970) · Zbl 0188.33102
[7] Book, R.; Greibach, S.; Wrathall, C., Reset machines, J. comput. system sci., 19, 256-276, (1979) · Zbl 0427.03029
[8] Book, R.; Nivat, M.; Paterson, M., Reversal-bounded acceptors and intersections of linear languages, SIAM J. comput., 3, 283-295, (1974) · Zbl 0292.68023
[9] Cartier, P.; Foata, D., Problèmes combinatoires de commutation et réarrangements, () · Zbl 0186.30101
[10] Clerbout, M., Effacement linéaire et commutation partitionnée, (1982), Publication de l’Equipe Lilloise d’Informatique Théorique, No. IT 41-82
[11] Culik, K., A purely homomorphic characterization of recursively enumerable sets, J. assoc. comput. match., 26, 345-350, (1979) · Zbl 0395.68076
[12] Engelfriet, J.; Rozenberg, G., Fixed point languages, equality languages and representation of recursively enumerable sets, J. assoc. comput. Mach., 27, 499-518, (1980) · Zbl 0475.68047
[13] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[14] Grabowski, J., On partial languages, Fundamenta informaticae, 4, 427-498, (1981) · Zbl 0468.68088
[15] Greibach, S., The unsolvability of the recognition of linear context-free languages, J. assoc. comput. Mach., 13, 582-587, (1966) · Zbl 0148.00901
[16] Knuth, E., Cycles of partial orders, MFCS, Zakopane, Lecture notes in computer science, 64, 315-325, (1978)
[17] Lallement, G., Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[18] Leguy, J., Transductions rationnelles décroissantes, RAIRO inform. théorique, 5, 141-148, (1981) · Zbl 0456.68097
[19] Mazurkiewicz, A., Concurrent program schemes and their interpretations, ()
[20] Rodriguez, F.; Schmitt, J.L., Autoshuffle et langages FIFO, ()
[21] Szijártó, M., A classification and closure properties of languages for describing concurrent system behaviours, Fundamenta informaticae, 4, 531-549, (1981) · Zbl 0486.68074
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.