Decidable cases of first-order temporal logic with functions
Studia Logica 88 (2):247 - 261 (2008)
| Abstract | We consider the decision problem for cases of first-order temporal logic with function symbols and without equality. The monadic monodic fragment with flexible functions can be decided with EXPSPACE-complete complexity. A single rigid function is sufficient to make the logic not recursively enumerable. However, the monadic monodic fragment with rigid functions, where no two distinct terms have variables bound by the same quantifier, is decidable and EXPSPACE-complete. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesSamuel Alexander (2013). The First-Order Syntax of Variadic Functions. Notre Dame Journal of Formal Logic 54 (1):47-59.
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
Alexander Paseau (2010). Pure Second-Order Logic with Second-Order Identity. Notre Dame Journal of Formal Logic 51 (3):351-360.
Nicolas Troquard, Wiebe Hoek & Michael Wooldridge (2011). Reasoning About Social Choice Functions. Journal of Philosophical Logic 40 (4):473-498.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Ian Hodkinson (2002). Monodic Packed Fragment with Equality is Decidable. Studia Logica 72 (2):185-197.
Natasha Alechina (1995). On a Decidable Generalized Quantifier Logic Corresponding to a Decidable Fragment of First-Order Logic. Journal of Logic, Language and Information 4 (3):177-189.
Roman Kontchakov, Carsten Lutz, Frank Wolter & Michael Zakharyaschev (2004). Temporalising Tableaux. Studia Logica 76 (1):91 - 134.
Savas Konur (forthcoming). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information.
Anatoli Degtyarev, Michael Fisher & Alexei Lisitsa (2002). Equality and Monodic First-Order Temporal Logic. Studia Logica 72 (2):147-156.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads15 ( #78,648 of 549,090 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
