A finite axiomatization of nondeterministic regular expressions

Flavio Corradini; Rocco De Nicola; Anna Labella

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1999)

  • Volume: 33, Issue: 4-5, page 447-465
  • ISSN: 0988-3754

How to cite

top

Corradini, Flavio, De Nicola, Rocco, and Labella, Anna. "A finite axiomatization of nondeterministic regular expressions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 33.4-5 (1999): 447-465. <http://eudml.org/doc/92614>.

@article{Corradini1999,
author = {Corradini, Flavio, De Nicola, Rocco, Labella, Anna},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {regular languages; regular expressions},
language = {eng},
number = {4-5},
pages = {447-465},
publisher = {EDP-Sciences},
title = {A finite axiomatization of nondeterministic regular expressions},
url = {http://eudml.org/doc/92614},
volume = {33},
year = {1999},
}

TY - JOUR
AU - Corradini, Flavio
AU - De Nicola, Rocco
AU - Labella, Anna
TI - A finite axiomatization of nondeterministic regular expressions
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 4-5
SP - 447
EP - 465
LA - eng
KW - regular languages; regular expressions
UR - http://eudml.org/doc/92614
ER -

References

top
  1. [1] L. Aceto and W. Fokkink, An Equational Axiomatization for multi-exit iteration. Inform. and Comput. 134 (1997) 121-158. Zbl0881.68069MR1468880
  2. [2] L. Aceto, W. Fokkink, R. van Glabbeek and A. Ingólfsdóttir, Axiomatizing prefix iteration with silent steps. Inform. and Comput 127 (1996) 26-40. Zbl0855.68030MR1394553
  3. [3] L. Aceto, W. Fokkink and A. Ingólfsdóttir, A managerie of non-finitely based process semantics over BPA*: From ready simulation to completed traces. Research Report, BRICS, RS-96-23 (1996). 
  4. [4] J. C. M. Baeten and J. A. Bergstra, Process Algebra with a Zero Object, in Proc. of Concu'90. Springer, Lecture Notes in Comput Sci. 458 (1990) 83-98. MR1082157
  5. [5] L. Bernatsky, S. L. Bloom, Z. Ésik and Gh. Stefanescu, Equational theories of relations and regular sets, in Proc. of Words, Languages and Combinatorics, Kyoto, 1992. Word Scientific, (1994) 40-48. Zbl0874.08002MR1351278
  6. [6] S. L. Bloom and Z. Ésik, Iteration Algebras of Finite State Process Behaviours. Manuscript. 
  7. [7] S. L. Bloom, Z. Ésik and D. Taubner, Iteration theories of synchronization trees. Inform. and Comput. 102 (1993) 1-55. Zbl0780.68088MR1201904
  8. [8] M. Boffa, Une remarque sur les systèmes complets d'identités rationelles. Theoret. Informatics Appl. 24 (1990) 419-423. Zbl0701.68059MR1079723
  9. [9] J. H. Conway, Regular Algebra and Finite Machines. Chapman and Hall, London (1971). Zbl0231.94041
  10. [10] F. Corradini, R. De Nicola and A. Labella, Fully Abstract Models for Nondeterministic Regular Expressions, in Proc. of Concur'95. Springer Verlag, Lecture Notes in Comput. Sci. 962 (1995) 130-144. 
  11. [11] F. Corradini, R. De Nicola and A. Labella, Models of Nondeterministic Regular Expressions. J. Comput. System Sci., to appear. Zbl0958.68090MR1726770
  12. [12] R. De Nicola and A. Labella, Tree Morphisms and Bisimulations, in Proc. of MFCS'98 Workshop on Concurrency. Elsevier, Amsterdam, Electron. Notes Theoret. Comput. Sci. 18 (1998). Zbl1206.68214MR1672349
  13. [13] R. De Nicola and A. Labella, A Completeness Theorem for Nondeterministic Kleene Algebras, in Proc. of MFCS'94. Springer, Lecture Notes in Comput. Sci. 841 (1994) 536-545. 
  14. [14] W. Fokkink, A complete equational axiomatization for prefix iteration. Inform. Process. Lett. 52 (1994) 333-337. Zbl0938.68697MR1307752
  15. [15] W. Fokkink, On the completeness of the Equations for the Kleene Star in Bisimulation, in Proc. of AMAST'96. Springer, Lecture Notes in Comput. Sci. 1101 (1996) 180-194. Zbl0886.03032MR1480695
  16. [16] W. Fokkink, Axiomatizations for the perpetual loop in Process Algebras, in Proc. of ICALP'97. Springer, Lecture Notes in Comput. Sci. 1256 (1997) 571-581. MR1616217
  17. [17] W. Fokkink and H. Zantema, Basic process algebra with iteration: Completeness of its equational axioms. Comput. J. 37 (1994) 259-267. 
  18. [18] C. A. R. Hoare, Communicating Sequential Processes. Prentice Hall (1989). Zbl0637.68007
  19. [19] S. C. Kleene, Representation of Events in Nerve Nets and Finite Automata, in Automata Studies, Shannon and McCarthy, Ed. Princeton Univ. Pr. (1956) 3-41. MR77478
  20. [20] S. Kasangian and A. Labella, Enriched Categorical Semantics for Distributed Calculi. J. Pure Appl. Algebra 83 (1992) 295-321. Zbl0777.18007MR1194841
  21. [21] D. Kozen, A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events. Inform. and Comput 110 (1994) 366-390. Zbl0806.68082MR1276741
  22. [22] D. Krob, Complete Systems of B-rational identities. Theoret. Comput. Sci. 89 (1991) 207-343. Zbl0737.68053MR1133622
  23. [23] W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer, Berlin, Monogr. Theoret. Comput. Sci. EATCS Ser. 5 (1986). Zbl0582.68002MR817983
  24. [24] R. Milner, A Calculus of Communicating Systems. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci. 94 (1980). Zbl0452.68027MR590046
  25. [25] R. Milner, A complete inference System for a class of regular behaviors. J. Comput. System Sci. 28 (1984) 439-466. Zbl0562.68065MR752442
  26. [26] R. Milner, Communication and Concurrency. Prentice Hall (1989). Zbl0683.68008
  27. [27] R. N. Moll, M. A. Arbib and A. J. Kfoury, An Introduction to Formal Language Theory. Springer-Verlag, Berlin (1987). Zbl0655.68002MR956253
  28. [28] D. Park, Concurrency and Automata on Infinite sequences, in Proc. GI. Springer, Lecture Notes in Comput. Sci. 104 (1981) 167-183. Zbl0457.68049
  29. [29] B. C. Pierce, Basic Category Theory for Computer Scientists. The MIT Press (1991). Zbl0875.18001MR1120026
  30. [30] V. N. Redko, On defining relations for the algebra of regular events (Russian). Ukrain. Mat. Z. 16 (1964) 120-126. MR179033
  31. [31] J. Sakarovitch, Kleene's theorem revisited, in Proc. of Trends, techniques, and problems in theoretical computer science. Springer, Lecture Notes in Comput. Sci. 281 (1986) 39-50. Zbl0637.68096MR921502
  32. [32] A. Salomaa, Two Complete Axiom Systems for the Algebra of Regular Events. J. ACM 13 (1966) 158-169. Zbl0149.24902MR189995
  33. [33] P. Sewell, Bisimulation is not finitely (first order) equationally axiomatisable, in Proc. of LICS'94 (1994). 
  34. [34] M. B. Smith and G. D. Piotkin, The category-Theoretic Solution of Recursive Domain Equation. SIAM J. Comput. 11 (1982) 762-783. Zbl0493.68022MR677666
  35. [35] D. R. Troeger, Step bisimulation is pomset equivalence on a parallel language without explicit internal choice. Math. Structures Comput. Sci. 3 (1993) 25-62. Zbl0806.68044MR1206871

NotesEmbed ?

top

You must be logged in to post comments.