Journal of Logic, Language and Information 14 (3):345-368 (2005)
Abstract |
Abstract State Machines (ASMs) provide a formal method for transparent design and specification of complex dynamic systems. They combine advantages of informal and formal methods. Applications of this method motivate a number of computability and decidability problems connected to ASMs. Such problems result for example from the area of verifying properties of ASMs. Their high expressive power leads rather directly to undecidability respectively uncomputability results for most interesting problems in the case of unrestricted ASMs. Consequently, it is rather natural to ask whether there exist expressive classes of ASMs for which we can prove positive decidability and computability results. In this work, we introduce such a class of ASMs. The concept is similar to the one of the guarded fragment of first-order logic. We analyze the expressive power of this class and prove that it is stronger than Datalog LITE and the guarded fragment of first-order fixed point logic. Some decidability and computability results have been proven in earlier works.
|
Keywords | Abstract State Machines guarded fragment expressive power Datalog LITE guarded fixed-point logic decidability computability |
Categories | (categorize this paper) |
DOI | 10.1007/s10849-005-5790-2 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Modal Languages and Bounded Fragments of Predicate Logic.Hajnal Andréka, István Németi & Johan van Benthem - 1998 - Journal of Philosophical Logic 27 (3):217 - 274.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Citations of this work BETA
No citations found.
Similar books and articles
Interpolation and Definability in Guarded Fragments.Eva Hoogland & Maarten Marx - 2002 - Studia Logica 70 (3):373 - 409.
Deciding Regular Grammar Logics with Converse Through First-Order Logic.Stéphane Demri & Hans De Nivelle - 2005 - Journal of Logic, Language and Information 14 (3):289-329.
Guards, Bounds, and Generalized Semantics.Johan van Benthem - 2005 - Journal of Logic, Language and Information 14 (3):263-279.
The Semijoin Algebra and the Guarded Fragment.Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz & Jan Van den Bussche - 2005 - Journal of Logic, Language and Information 14 (3):331-343.
Guarded Fragments with Constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic 14 (3):281-288.
Loosely Guarded Fragment of First-Order Logic has the Finite Model Property.Ian Hodkinson - 2002 - Studia Logica 70 (2):205 - 240.
Guarded Fragments with Constants.Balder ten Cate & Massimo Franceschet - 2005 - Journal of Logic, Language and Information 14 (3):281-288.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Analytics
Added to PP index
2009-01-28
Total views
89 ( #129,476 of 2,499,084 )
Recent downloads (6 months)
1 ( #419,059 of 2,499,084 )
2009-01-28
Total views
89 ( #129,476 of 2,499,084 )
Recent downloads (6 months)
1 ( #419,059 of 2,499,084 )
How can I increase my downloads?
Downloads