article

First-order linear logic without modalities is NEXPTIME-hard

Authors:

P. Lincoln,

A. ScedrovAuthors Info & Claims

Theoretical Computer Science, Volume 135, Issue 1

Pages 139 - 153

https://doi.org/10.1016/0304-3975(94)00107-3

Published: 01 April 1992 Publication History

Abstract

No abstract available.

Cited By

View all

Horne RTiu AAman BCiobanu G(2019)De Morgan Dual Nominal Quantifiers Modelling Private Names in Non-Commutative LogicACM Transactions on Computational Logic10.1145/332582120:4(1-44)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3325821
Beckmann ABuss S(2014)Improved witnessing and local improvement principles for second-order bounded arithmeticACM Transactions on Computational Logic10.1145/255995015:1(1-35)Online publication date: 6-Mar-2014
https://dl.acm.org/doi/10.1145/2559950
Bauer M(2014)A PSPACE-complete first-order fragment of computability logicACM Transactions on Computational Logic10.1145/255994915:1(1-11)Online publication date: 6-Mar-2014
https://dl.acm.org/doi/10.1145/2559949
Show More Cited By

Index Terms

First-order linear logic without modalities is NEXPTIME-hard
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Logic programming and answer set programming
2. Theory of computation
  1. Logic
    1. Constraint and logic programming

Recommendations

The Succinctness of First-Order Logic on Linear Orders
LICS '04: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science

Succinctness is a natural measure for comparing the strength of different logics.Intuitively, a logic L is more succinct than another logic L if all properties that can be expressed in L can be expressed in L by formulas of (approximately) the same size,...
Proving Isomorphism of First-Order Logic Proof Systems in HOL
First-Order Modal Logic: Frame Definability and a Lindström Theorem

We generalize two well-known model-theoretic characterization theorems from propositional modal logic to first-order modal logic (FML, for short). We first study FML-definable frames and give a version of the Goldblatt---Thomason theorem for this logic. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 135, Issue 1

Dec. 5, 1994

161 pages

ISSN:0304-3975

Editors:
M. Nivat
Univ. de Paris VII, Moiselles, France
,
M. W. Mislove
Tulane Univ., New Orleans, LA
,
G. M. Reed
Tulane Univ., New Orleans, LA
,
A. W. Roscoe
Tulane Univ., New Orleans, LA
,
R. F. Wachter
Tulane Univ., New Orleans, LA

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 April 1992

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Horne RTiu AAman BCiobanu G(2019)De Morgan Dual Nominal Quantifiers Modelling Private Names in Non-Commutative LogicACM Transactions on Computational Logic10.1145/332582120:4(1-44)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3325821
Beckmann ABuss S(2014)Improved witnessing and local improvement principles for second-order bounded arithmeticACM Transactions on Computational Logic10.1145/255995015:1(1-35)Online publication date: 6-Mar-2014
https://dl.acm.org/doi/10.1145/2559950
Bauer M(2014)A PSPACE-complete first-order fragment of computability logicACM Transactions on Computational Logic10.1145/255994915:1(1-11)Online publication date: 6-Mar-2014
https://dl.acm.org/doi/10.1145/2559949
Cervesato IScedrov A(2009)Relating state-based and process-based concurrency through linear logic (full-version)Information and Computation10.1016/j.ic.2008.11.006207:10(1044-1077)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1016/j.ic.2008.11.006
Beckman NBierhoff KAldrich J(2008)Verifying correct usage of atomic blocks and typestateACM SIGPLAN Notices10.1145/1449955.144978343:10(227-244)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449955.1449783
Beckman NBierhoff KAldrich JHarris GKiczales GRiehle DBlack A(2008)Verifying correct usage of atomic blocks and typestateProceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications10.1145/1449764.1449783(227-244)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449764.1449783
Bierhoff KAldrich J(2007)Modular typestate checking of aliased objectsACM SIGPLAN Notices10.1145/1297105.129705042:10(301-320)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297105.1297050
Bierhoff KAldrich JGabriel RBacon DLopes CSteele G(2007)Modular typestate checking of aliased objectsProceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications10.1145/1297027.1297050(301-320)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297027.1297050
Bozzano MDelzanno GMartelli M(2004)Model checking linear logic specificationsTheory and Practice of Logic Programming10.1017/S14710684040020664:5-6(573-619)Online publication date: 1-Sep-2004
https://dl.acm.org/doi/10.1017/S1471068404002066
Mandelbaum YWalker DHarper R(2003)An effective theory of type refinementsACM SIGPLAN Notices10.1145/944746.94472538:9(213-225)Online publication date: 25-Aug-2003
https://dl.acm.org/doi/10.1145/944746.944725
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

The Succinctness of First-Order Logic on Linear Orders

Proving Isomorphism of First-Order Logic Proof Systems in HOL

First-Order Modal Logic: Frame Definability and a Lindström Theorem

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations