A decision algorithm for linear sentences on a PFM

Annals of Pure and Applied Logic 59 (3):273-286 (1993)
  Copy   BIBTEX

Abstract

By PFM, we mean a finitely generated module over a principal ideal domain; a linear sentence is a sentence that contains no disjunctive and negative symbols. In this paper, we present an algorithm which decides the truth for linear sentences on a given PFM, and we discuss its time complexity. In particular, when the principal ideal domain is the ring of integers or a univariate polynomial ring over the field of rationals, the algorithm is polynomial-time. Finally, we consider some applications to Abelian groups

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 102,440

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Definable combinatorics with dense linear orders.Himanshu Shukla, Arihant Jain & Amit Kuber - 2020 - Archive for Mathematical Logic 59 (5-6):679-701.
Complexity of monodic guarded fragments over linear and real time.Ian Hodkinson - 2006 - Annals of Pure and Applied Logic 138 (1):94-125.
Scott sentences for certain groups.Julia F. Knight & Vikram Saraph - 2018 - Archive for Mathematical Logic 57 (3-4):453-472.
Model theory of modules over a serial ring.Paul C. Eklof & Ivo Herzog - 1995 - Annals of Pure and Applied Logic 72 (2):145-176.
Consistency, optimality, and incompleteness.Yijia Chen, Jörg Flum & Moritz Müller - 2013 - Annals of Pure and Applied Logic 164 (12):1224-1235.
Computing Congruences Efficiently.Ralph Freese - 2008 - Algebra Universalis 59 (3):337–343.
Linear logic with fixed resources.Dmitry A. Archangelsky & Mikhail A. Taitslin - 1994 - Annals of Pure and Applied Logic 67 (1-3):3-28.

Analytics

Added to PP
2014-01-16

Downloads
44 (#519,147)

6 months
7 (#658,938)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

The computational complexity of logical theories.Jeanne Ferrante - 1979 - New York: Springer Verlag. Edited by Charles W. Rackoff.

Add more references