Zobrazeno 1 - 10
of 1 303
pro vyhledávání: '"Recursively enumerable language"'
Autor:
Henning Fernau, Martin Vu
Publikováno v:
Beyond the Horizon of Computability
In this paper, we discuss the addition of substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems, i.e., in addition to insertions and deletions we allow single letter replacements to occur. We invest
Publikováno v:
Journal of Membrane Computing. 4:68-86
A Szilard language is a well-known tool in formal language theory to express the derivation process in a grammar system or grammar. Matrix InsDel (insertion–deletion) system is a well-known variant of InsDel system, where the idea of matrix control
Publikováno v:
Theoretical Computer Science. 893:60-71
Spiking neural P systems with rules on synapses (RSSNP systems) are a class of computation models which are inspired by the information processing and communication manner of neurons. In this work, we consider labeled RSSNP systems (lRSSNP systems),
Publikováno v:
Communications of the ACM. 64:131-138
Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated eno
Publikováno v:
Natural Computing. 20:671-689
A matrix insertion-deletion system (or matrix ins-del system) is described by a set of insertion-deletion rules presented in matrix form, which demands all rules of a matrix to be applied in the given order. These systems were introduced to model ver
Publikováno v:
Journal of Membrane Computing
Journal of Membrane Computing, 2021, 3, pp.170--181. ⟨10.1007/s41965-021-00079-x⟩
Journal of Membrane Computing, 2021, 3, pp.170--181. ⟨10.1007/s41965-021-00079-x⟩
Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particular the problem of using only one catalyst in th
Autor:
Mikhail N. Rybakov, Dmitry Shkatov
Publikováno v:
Journal of Logic and Computation. 31:1266-1288
We study the algorithmic properties of first-order monomodal logics of frames $\langle {\textrm{I}\!\textrm{N}}, \leqslant \rangle $, $\langle {\textrm{I}\!\textrm{N}}, < \rangle $, $\langle \mathbb {Q}, \leqslant \rangle $, $\langle \mathbb {Q}, < \
Autor:
Stepan L. Kuznetsov
Publikováno v:
ACM Transactions on Computational Logic. 22:1-26
Action logic is the algebraic logic (inequational theory) of residuated Kleene lattices. One of the operations of this logic is the Kleene star, which is axiomatized by an induction scheme. For a stronger system that uses an -rule instead (infinitary
Publikováno v:
Proceedings of the ACM on Programming Languages
Proceedings of the ACM on Programming Languages, 2021, ⟨10.1145/3434313⟩
Proceedings of the ACM on Programming Languages, ACM, 2021, ⟨10.1145/3434313⟩
Proceedings of the ACM on Programming Languages, 2021, ⟨10.1145/3434313⟩
Proceedings of the ACM on Programming Languages, ACM, 2021, ⟨10.1145/3434313⟩
Randomized higher-order computation can be seen as being captured by a λ-calculus endowed with a single algebraic operation, namely a construct for binary probabilistic choice. What matters about such computations is the probability of obtaining any
Publikováno v:
Theoretical Computer Science. 851:77-91
Inspired from spiking and dynamic mechanisms of neurons, dynamic threshold neural P systems (DTNP systems) have been developed and their computational completeness as number-generating/accepting devices and function computing devices has been investi