On Fork Arrow Logic and its Expressive Power |
| |
Authors: | Paulo A. S. Veloso Renata P. de Freitas Petrucio Viana Mario Benevides Sheila R. M. Veloso |
| |
Affiliation: | (1) Systems and Computer Engineering Program, COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, 21945-970 Rio de Janeiro, RJ, Brazil;(2) Institute of Mathematics, Universidade Federal Fluminense, Rua Mario Santos Braga, s/m, 24210-340 Niterói, RJ, Brazil;(3) Institute of Mathematics, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, 21945-970 Rio de Janeiro, RJ, Brazil;(4) Systems and Computer Engin. Dept., Faculty of Engineering, Universidade Estadual do Rio de Janeiro, Rua Sao Francisco Xavier 524, 21945-970 Rio de Janeiro, RJ, Brazil |
| |
Abstract: | We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order correspondence language, so both can express the same input–output behavior of processes. |
| |
Keywords: | arrow logic expressive power fork algebra modal logic relation algebra standard translation |
本文献已被 SpringerLink 等数据库收录! |
|