The power of synchronizing operations on strings. (English) Zbl 0477.68034


68Q65 Abstract data types; algebraic specification
68Q45 Formal languages and automata
03D25 Recursively (computably) enumerable sets and degrees
03B25 Decidability of theories and sets of sentences
Full Text: DOI


[1] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[2] Greibach, S.A., Remarks on blind and partially blind one-way multicounter machines, Theoret. comput. sci., 7, 311-324, (1978) · Zbl 0389.68030
[3] Jantzen, M., On the hierarchy of Petri net languages, R.A.I.R.O. — informatique théorique, 13, 19-30, (1979) · Zbl 0404.68076
[4] Jantzen, M., Eigenschaften von petrinetzsprachen, (1979), Univ. Hamburg, Fachbereich Informatik, dissertation
[5] Jantzen, M., On zerotesting — bounded multicounter machines, (), 158-169 · Zbl 0411.68070
[6] Kimura, T., An algebraic system for process structuring and interprocess communication, Proc. 8th annual ACM symposium on theory of computing, 92-100, (1976) · Zbl 0365.68066
[7] Kimura, T., Formal description of communication behaviour, Proc. johns hopkins conference on information sciences and systems, (1979)
[8] Ogden, W.F.; Riddle, W.E.; Rounds, W.C., Complexity of expressions allowing concurrency, Proc. 5th annual ACM symposium on principles of programming languages, 185-194, (1978)
[9] Riddle, W.E., Modelling and analysis of supervisor systems, ()
[10] Riddle, W.E., Software systems modelling and analysis, () · Zbl 0408.68031
[11] Shaw, A.C., Systems design and documentation using path descriptions, (), 180-181
[12] Shaw, A.C., Software description with flow expressions, IEEE trans. software engrg., 3, 4, 242-254, (1978) · Zbl 0381.68035
[13] Slutzki, G., Non-synchronizing concurrent processes and their languages, (1979), Department of Computer and Information Sciences, University of Delaware Newark, unpublished manuscript
[14] Slutzki, G., Descriptional complexity of concurrent processes, (1979), Department of Computer and Information Sciences, University of Delaware Newark, unpublished manuscript
[15] Hall, M., Combinatorial theory, (1967), Blaisdell Waltham, MA · Zbl 0196.02401
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.