Interval-valued computations and their connection with PSPACE

DOI10.1016/J.TCS.2007.12.013MaRDI QIDQ2482463zbMATH OpenOpenAlexFDO

Authors Benedek Nagy, Sándor Vályi

Publication date 16 April 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.12.013

zbMATH Keywords

algorithmic complexitynew computing paradigmsparallel computing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Interval computations and their categorification
• A characterization of NP within interval-valued computing
• Interval-valued Iq^b-calculus and applications
• Interval Space Representation of interval Structures
• Interval-Valued Intuitionistic Multiplicative Sets
• Interval-valued intuitionistic sets and their application to topology
• Complexity of interpolation and related problems in positive calculi
• scientific article; zbMATH DE number 903769
• scientific article; zbMATH DE number 808820
• Computable structures and operations on the space of continuous functions

Cites work

• An optical model of computation
• Analog computation via neural networks
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 50007 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• Maintaining knowledge about temporal intervals
• Membrane computing. An introduction.
• Non-Turing computations via Malament--Hogarth space-times
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• SOFSEM 2006: Theory and Practice of Computer Science
• The CNN universal machine: an analogic array computer

Cited in

(6)

• An extension of interval-valued computing equivalent to red-green Turing machines
• Prime factorization by interval-valued computing
• Non-isometric contextual array grammars with regular control and local selectors
• A characterization of NP within interval-valued computing
• Circular interval-valued computers and simulation of (red-green) Turing machines
• Interval-valued computations without the product operator

This page was built for publication: Interval-valued computations and their connection with PSPACE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482463)