The basic framework of domain -calculus was formulated in [39] more than ten years ago. This paper provides an improved formulation of a fragment of the -calculus without function space or powerdomain constructions, and studies some open problems related to this -calculus such as decidability and expressive power. A class of language equations is introduced for encoding -formulas in order to derive results related to decidability and expressive power of non-trivial fragments of the domain -calculus. The existence and uniqueness of solutions to this class of language equations constitute an important component of this approach. Our formulation is based on the recent work of Leiss [23], who established a sophisticated framework for solving language equations using Boolean automata (a.k.a. alternating automata [12, 35]) and a generalized notion of language derivatives. Additionally, the early notion of even-linear grammars is adopted here to treat another fragment of the domain -calculus.
Keywords: domain theory, mu-calculus, formal languages, boolean automata
@article{ITA_2003__37_4_337_0,
author = {Zhang, Guo-Qiang},
title = {Domain mu-calculus},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {337--364},
year = {2003},
publisher = {EDP-Sciences},
volume = {37},
number = {4},
doi = {10.1051/ita:2003023},
mrnumber = {2053031},
zbl = {1038.03038},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2003023/}
}
TY - JOUR AU - Zhang, Guo-Qiang TI - Domain mu-calculus JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2003 SP - 337 EP - 364 VL - 37 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2003023/ DO - 10.1051/ita:2003023 LA - en ID - ITA_2003__37_4_337_0 ER -
%0 Journal Article %A Zhang, Guo-Qiang %T Domain mu-calculus %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 337-364 %V 37 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2003023/ %R 10.1051/ita:2003023 %G en %F ITA_2003__37_4_337_0
Zhang, Guo-Qiang. Domain mu-calculus. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 4, pp. 337-364. doi: 10.1051/ita:2003023
Cité par Sources :