×
Aalbersberg, Ijsbrand Jan; Welzl, Emo

Trace languages defined by regular string languages. (English) Zbl 0612.68071

RAIRO, Inf. Théor. Appl. 20, 103-119 (1986).
A concurrent alphabet is a pair \({\mathcal C}=<\Sigma,C>\), where \(\Sigma\) is an alphabet and C is a relation over \(\Sigma\), called the concurrency relation. Two words over \(\Sigma\) are called C-equivalent, if they can be obtained from each other by successively interchanging adjacent symbols which are related to C. A trace (over \({\mathcal C})\) is now simply an equivalence class with respect to C-equivalence. We consider trace languages (i.e., sets of traces) as they are defined by regular string languages in the following ways: (i) existentially regular trace languages (the trace language defined existentially by a regular string language L consists of all traces which have a representative in L), (ii) universally regular trace languages (the trace language defined universally by a regular string language L consists of all traces which have all representatives in L), and (iii) consistently regular trace languages (a regular string language L defines a consistently regular trace language T if and only if L is the union of all the traces in T).
In particular, the main result characterizes those concurrent alphabets for which the family of existentially regular trace languages equals the family of universally regular trace languages. Furthermore, using this result, a number of decidability results and characterizations of closure properties for the three above mentioned families of trace languages are derived.

Cited in 13 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

concurrent alphabet; concurrency relation; existentially regular trace languages; universally regular trace languages; decidability; closure properties
PDF BibTeX XML Cite
\textit{I. J. Aalbersberg} and \textit{E. Welzl}, RAIRO, Inform. Théor. Appl. 20, 103--119 (1986; Zbl 0612.68071)
Full Text: DOI EuDML

References:

[1] 1. IJ.J. AALBERSBERG and G. ROZENBERG, Traces - a Survey, Techn. Rep. 85-16, Inst. of Appl. Math. and Comput. Sc., Univ. of Leiden, Leiden, 1985.
[2] 2. IJ. J. AALBERSBERG and G. ROZENBERG, Traces, Dependency Graphs and DNLC Grammars, Discrete Appl. Math, Vol. 11, 1985, pp.299-306. Zbl0601.68045 MR792896 · Zbl 0601.68045
[3] 3. A. BERTONI, M. BRAMBILLA, G. MAURI and N. SABADINI, An Application of the Theory of Free Partially Commutative Monoids : Asymptotic Densities of Trace Languages, Lecture Notes in Computer Science, Vol. 118, 1981, pp. 205-215. Zbl0468.68081 · Zbl 0468.68081
[4] 4. A. BERTONI, G. MAURI and N. SABADINI, A Hierarchy of Regular Trace Languages and Sorne Combinatorial Applications, Proc. 2nd.World Conf. on Math, at the Service of Men, Las Palmas, 1982, pp.146-153. Zbl0512.68056 · Zbl 0512.68056
[5] 5. A. BERTONI, G. MAURI and N. SABADINI, Equivalence and Membership Problems for Regular Trace Languages, Lecture Notes in Computer Science, Vol. 140, 1982, pp. 61-71. Zbl0486.68079 MR675445 · Zbl 0486.68079
[6] 6. A. BERTONI, G. MAURI and N. SABADINI, Unambiguous Regular Trace Languages, to appear in Algebra, Combinatorics and Logic in Comput. Sc. (to appear), Colloquia Math. Soc. J. Bolay. Zbl0627.68060 MR875858 · Zbl 0627.68060
[7] 7. R. CORI and D. PERRIN, Automates et Commutations Partielles, R.A.I.R.O., Inform. Théor., Vol. 19, 1985, pp. 21-32. Zbl0601.68055 MR795769 · Zbl 0601.68055
[8] 8. M. FLEISS, Matrices de Hankel, J. Math. Pures Appl., Vol. 53, 1974, pp. 197-222. Zbl0315.94051 MR364328 · Zbl 0315.94051
[9] 8. S. GINSBURG, The Mathematical Theory of Context Free Languages, Mc-Graw-Hill Book Company, New York, London, 1966. Zbl0184.28401 MR211815 · Zbl 0184.28401
[10] 10. J. E. HOPCROFT and J. D. ULLMAN, Introduction to automata theory, languages and computation, Addison -Wesley, Reading, Mass, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[11] 11. G. LALLEMENT, Semigroups and combinatorial applications, J. Wiley and Sons, New York, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[12] 12. A. MAZURKIEWICZ, Concurrent Program Schemes and Their Interpretations, DAIMI Rep. PB-78, Aarhus Univ., Aarhus, 1977.
[13] 13. A. MAZURKIEWICZ, Traces, Histories, Graphs: Instances of a Process Monoid, Lecture Notes in Computer Science, Vol. 176, 1984, pp.115-133. Zbl0577.68061 MR783441 · Zbl 0577.68061
[14] 14. A. MAZURKIEWICZ, Semantics of Concurrent Systems: a Modular Fixed-Point Trace Approach, Lecture Notes in Computer Science, Vol. 188, 1985, pp.353-375. Zbl0576.68044 MR807209 · Zbl 0576.68044
[15] 15. J. SAKAROVITCH, On Regular Trace Languages, R.A.I.R.O., Inform. Théor. (to appear). MR918113
[16] 16. A. SALOMAA, Theory of automata, Pergamon Press, Oxford - New York, 1969. Zbl0193.32901 MR262021 · Zbl 0193.32901
[17] 17. A. SALOMAA, Formal languages, Academic Press, New York, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
[18] 18. M. SZIJARTO, A Classification and Closure Properties of Languages for Describing Concurrent System Behaviours, Fund. Inform., Vol. 4, 1981, pp. 531-549. Zbl0486.68074 MR678010 · Zbl 0486.68074
[19] 19. A. TARLECKI, Notes on the Implementability of Formal Languages by Concurrent Systems, ICS PAS Rep. 481, Inst. of Comput. Sc., Polish Acad. of Sc., Warshaw, 1982.
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.