Search

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 investigate the effect of the addition of substitution rules on the context dependency of such systems, thereby also obtaining new characterizations of and even normal forms for context-sensitive (CS) and recursively enumerable (RE) languages and their phrase-structure grammars. More specifically, we prove that for each RE language, there is a system generating this language that only inserts and deletes strings of length two without considering the context of the insertion or deletion site, but which may change symbols (by a substitution operation) by checking a single symbol to the left of the substitution site. When we allow checking left and right single-letter context in substitutions, even context-free insertions and deletions of single letters suffice to reach computational completeness. When allowing context-free insertions only, checking left and right single-letter context in substitutions gives a new characterization of CS. This clearly shows the power of this new type of rules.

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 is combined with InsDel systems. The size of a matrix InsDel system is represented by a septuple of integers $$(k; p, m, m^{'};$$ $$q, n, n^{'})$$ , where k represents maximum number of rules in a matrix, i.e., size of a matrix. The parameters p, m and $$m^{'}$$ represent the maximal length of the strings inserted, the maximal length of the left context and the maximal length of the right context of the insertion rules, respectively. The parameters $$q, n, n^{'}$$ represent the same for deletion rules. In this paper, we investigate the Szilard languages of matrix InsDel systems with matrices of size 2. We give examples of regular, context-free and context-sensitive languages which cannot be the Szilard language of any matrix InsDel system. We show that any regular language can be represented as a homomorphic image of Szilard language of matrix InsDel system of size (2; 2, 0, 0; 1, 0, 0). Any linear language, meta-linear language and rational (or regular) closure of linear language can be obtained as the homomorphic image of Szilard language of matrix InsDel systems of size (2; 1, 1, 0; 1, 1, 0), and (2; 1, 0, 1; 1, 0, 1). Moreover, any recursively enumerable language can be obtained as the homomorphic image of the Szilard language of matrix InsDel systems of size (2; 1, 1, 0; 1, 1, 1), (2; 1, 0, 1; 1, 1, 1), (2; 1, 1, 1; 1, 1, 0), (2; 1, 1, 1; 1, 0, 1), (2; 1, 1, 0; 2, 0, 0), (2; 1, 0, 1; 2, 0, 0), (2; 2, 0, 0; 1, 1, 0), and (2; 2, 0, 0; 1, 0, 1).

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), where each rule is assigned either with a label chosen from an alphabet Σ or with the empty label λ. A string over an alphabet is accepted by an lRSSNP system if the string is processed from left to right by the system in the sense that in a step only rules labeled with the processed symbol or with λ are used (not both), and the system reaches a final configuration in the moment when the whole string is processed. The set of all accepted strings is categorized as the restricted (computations are done with the application of the rules labeled with symbols from the given alphabet) control language and the unrestricted (rules labeled with λ are allowed in the computations) control language of the system. We study the language accepting power of lRSSNP systems using only standard spiking rules by comparing the family of control languages of lRSSNP systems with the families of languages in the Chomsky hierarchy. It is proved that restricted lRSSNP systems can accept no more than context-sensitive languages, and unrestricted lRSSNP systems can accept recursively enumerable languages.

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 enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers. The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).

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 very simplistic fragments of sequential programs based on insertion and deletion as elementary operations as can be found in biocomputing. We are investigating such systems with limited resources as formalized in descriptional complexity. A traditional descriptional complexity measure of such a matrix ins-del system is its size $$s=(k;n,i',i'';m,j',j'')$$ s = ( k ; n , i ′ , i ′ ′ ; m , j ′ , j ′ ′ ) , where the parameters from left to right represent the maximal matrix length, maximal insertion string length, maximal length of left contexts in insertion rules, maximal length of right contexts in insertion rules; the last three are deletion counterparts of the previous three parameters. We call the sum $$n+i'+i''+m+j'+j''$$ n + i ′ + i ′ ′ + m + j ′ + j ′ ′ the sum-norm of s. We show that matrix ins-del systems of sum-norm 4 and sizes (3; 1, 0, 0; 1, 2, 0), (3; 1, 0, 0; 1, 0, 2), (2; 1, 2, 0; 1, 0, 0), (2; 1, 0, 2; 1, 0, 0), and (2; 1, 1, 1; 1, 0, 0) describe the recursively enumerable languages. Moreover, matrix ins-del systems of sizes (3; 1, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), (2; 2, 1, 0; 1, 0, 0) and (2; 2, 0, 1; 1, 0, 0) can describe at least the regular closure of the linear languages. In fact, we show that if a matrix ins-del system of size s can describe the class of linear languages $$\mathrm {LIN}$$ LIN , then without any additional resources, matrix ins-del systems of size s also describe the regular closure of $$\mathrm {LIN}$$ LIN . Finally, we prove that matrix ins-del systems of sizes (2; 1, 1, 0; 1, 1, 0) and (2; 1, 0, 1; 1, 0, 1) can describe at least the regular languages.

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 the whole system: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining computational completeness even with only one catalyst. In this paper, we show that one catalyst is sufficient for obtaining computational completeness if either catalytic rules have weak priority over non-catalytic rules or else instead of the standard maximally parallel derivation mode, we use the derivation mode maxobjects, i.e., we only take those multisets of rules which affect the maximal number of objects in the underlying configuration.

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}, < \rangle $, $\langle {\textrm{I}\!\textrm{R}}, \leqslant \rangle $, $\langle {\textrm{I}\!\textrm{R}}, < \rangle $, as well as some related logics, in languages with restrictions on the number of individual variables as well as the number and arity of predicate letters. We show that the logics of frames based on $ {\textrm{I}\!\textrm{N}}$ are $\varPi ^1_1$-hard—thus, not recursively enumerable—in languages with two individual variables, one monadic predicate letter and one proposition letter. We also show that the logics of frames based on $\mathbb {Q}$ and ${\textrm{I}\!\textrm{R}}$ are $\varSigma ^0_1$-hard in languages with the same restrictions. Similar results are obtained for a number of related logics.

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 action logic), Buszkowski and Palka (2007) proved -completeness (thus, undecidability). Decidability of action logic itself was an open question, raised by Kozen in 1994. In this article, we show that it is undecidable, more precisely, -complete. We also prove the same undecidability results for all recursively enumerable logics between action logic and infinitary action logic, for fragments of these logics with only one of the two lattice (additive) connectives, and for action logic extended with the law of distributivity.

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 given result, rather than the possibility or the necessity of obtaining it, like in (non)deterministic computation. Termination, arguably the simplest kind of reachability problem, can be spelled out in at least two ways, depending on whether it talks about the probability of convergence or about the expected evaluation time, the second one providing a stronger guarantee. In this paper, we show that intersection types are capable of precisely characterizing both notions of termination inside a single system of types: the probability of convergence of any λ-term can be underapproximated by its type , while the underlying derivation’s weight gives a lower bound to the term’s expected number of steps to normal form. Noticeably, both approximations are tight—not only soundness but also completeness holds. The crucial ingredient is non-idempotency, without which it would be impossible to reason on the expected number of reduction steps which are necessary to completely evaluate any term. Besides, the kind of approximation we obtain is proved to be optimal recursion theoretically: no recursively enumerable formal system can do better than that.

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 investigated. However, a universality result of DTNP systems as language generators has not been established so far. This paper discusses computational power of DTNP systems as language generators. We first discuss the relationship between the languages generated by DTNP systems and finite languages, and then prove that regular languages can be generated by finite DTNP systems. Moreover, we prove that recursively enumerable languages can be characterized by projections of inverse-morphic images of the languages generated by DTNP systems.

Cell-like P systems with promoters/inhibitors (PIC-P systems) are a class of distributed and parallel computing models inspired by the function of regulating biochemical reactions by enzymes in biological cells. In PIC-P systems, each evolution rule (rule for short) can be associated with one promoter/inhibitor which helps control the evolution process of objects. In this work, we propose a novel variant of PIC-P systems, called time-free cell-like P systems with multi-promoters/inhibitors (time-free MPIC-P systems for short). In such systems, each rule can be associated with multiple promoters/inhibitors, and the execution time of each rule is extended from one time unit to a random number of time units. These two characters make the time-free MPIC-P systems closer to biological cells. We also investigate the computational power of time-free MPIC-P systems. As results, it is achieved by simulating the matrix grammar that such systems can generate the set of lengths of recursively enumerable languages, that is, Turing universality can be achieved. This indicates that the time-free working mode will not reduce the computational power of PIC-P systems, by using multiple promoters/inhibitors.

Neither the existence nor the nonexistence of a liveness enforcing supervisory policy (LESP) for an arbitrary Petri net (PN) is semidecidable. In an attempt to identify decidable instances, we explore the decidability of certain properties of the set of initial markings for which an LESP exists, and the decidability of the existence of a specific class of LESPs. We first prove that for an arbitrary PN structure, determining if there is an initial marking, or there are no initial markings, for which there is an LESP, is not semidecidable. Then, we characterize the class of PN structures for which the set of all initial markings for which an LESP exists is right-closed . We show that testing membership, or nonmembership, of an arbitrary PN in this class of PNs is not semidecidable. We then consider a restricted class of LESPs, called marking monotone LESPs (MM-LESPs). We show that the existence of an MM-LESP for an arbitrary PN is decidable.

We give a proof-theoretic and algorithmic complexity analysis for systems introduced by Morrill to serve as the core of the CatLog categorial grammar parser. We consider two recent versions of Morrill’s calculi, and focus on their fragments including multiplicative (Lambek) connectives, additive conjunction and disjunction, brackets and bracket modalities, and the ! subexponential modality. For both systems, we resolve issues connected with the cut rule and provide necessary modifications, after which we prove admissibility of cut (cut elimination theorem). We also prove algorithmic undecidability for both calculi, and show that categorial grammars based on them can generate arbitrary recursively enumerable languages.

In this paper, we associate the idea of derivation languages with a restricted variant of flat splicing systems where at each step splicing is done with an element from the initial set of words present in the system. We call these flat splicing systems as restricted flat splicing systems. We show that the families of Szilard languages of labeled restricted flat finite splicing systems of type ( m , n ) and REG, CF and CS are incomparable. Also, any non-empty regular, non-empty context-free and recursively enumerable language can be obtained as homomorphic image of the Szilard language of the labeled restricted flat finite splicing systems of type ( 1 , 2 ) , ( 2 , 2 ) and ( 5 , 2 ) respectively. We also introduce the idea of control languages for restricted labeled flat finite splicing systems and show that any non-empty regular and context-free language can be obtained as a control language of labeled restricted flat finite splicing systems of type ( 1 , 2 ) and ( 2 , 2 ) respectively. At the end, we show that any recursively enumerable language can be obtained as a control language of labeled restricted flat finite splicing systems of type ( 5 , 2 ) when λ-labeled rules are allowed.

Wireless communication systems are inherently vulnerable to intentional jamming. In this paper, two classes of such jammers are considered: those with partial and full knowledge. While the first class accounts for those jammers that know the encoding and decoding function, the latter accounts for those that are further aware of the actual transmitted message. Of particular interest are so-called denial-of-service (DoS) attacks in which the jammer is able to completely disrupt any transmission. Accordingly, it is of crucial interest for the legitimate users to detect such adversarial DoS attacks. This paper develops a detection framework based on Turing machines. Turing machines have no limitations on computational complexity and computing capacity and storage and can simulate any given algorithm. For both scenarios of a jammer with partial and full knowledge, it is shown that there exists no Turing machine which can decide whether or not a DoS attack is possible for a given channel and the corresponding decision problem is undecidable. On the other hand, it is shown for both scenarios that it is possible to algorithmically characterize those channels for which a DoS attack is not possible. This means that it is possible to detect those scenarios in which the jammer is not able to disrupt the communication. For all other channels, the Turing machine does not stop and runs forever making this decision problem semidecidable. Finally, it is shown that additional coordination resources such as common randomness make the communication robust against such attacks.

Context-dependent fusion grammars were recently introduced as devices for the generation of hypergraph languages. In this paper, we show that this new type of hypergraph grammars, where the application of fusion rules is restricted by positive and negative context conditions, is a universal computation model. Our main result is that Turing machines can be transformed into these grammars such that the recognized language of the Turing machine and the generated language of the corresponding context-dependent fusion grammar coincide up to representation of strings as graphs. As a corollary we get that context-dependent fusion grammars can generate all recursively enumerable string languages., Comment: In Proceedings GCM 2019, arXiv:1912.08966

What can be Computed is a textbook for a course that covers Decidable Languages, Computable Functions, Recursively Enumerable Languages, Turing Machines, Reductions, Regular Languages, P, NP, and NPcompleteness. Since there are already many books with these topics in them, the question is

Insertion–deletion (or ins–del for short) systems are simple models of bio-inspired computing. They are well studied in formal language theory, especially regarding their computational completeness. This concerns the question if all recursively enumerable languages can be generated. This ultimately addresses the question if one can build general-purpose computers rooted in this formalism. The descriptional complexity of an ins–del system is typically measured by its size, a 6-dimensional tuple of non-negative integers $$(e,e',e'';d,d',d'')$$ where e is the maximum length of the insertion string, $$e'$$ (and $$e''$$ ) is the maximum length of the left (and right) context used for insertion; the last three parameters $$d,d',d''$$ are similarly understood for deletion rules. Computational completeness for ins–del systems can even be achieved with rule size (1, 1, 1; 1, 1, 1) but with no rule size strictly smaller than this. This fact has motivated to study ins–del systems in combination with regulation mechanisms. In this context, the six-tuple explained above is called the ID size of a system. Several regulations like graph-control, matrix and semi-conditional have been imposed on ins–del systems. Typically, the computational completeness results are obtained as trade-offs, reducing the ID size, say, to (1, 1, 0; 1, 1, 0) at the expense of increasing other measures of descriptional complexity. In this paper, we study simple semi-conditional ins–del systems, where an ins–del rule can be applied only in the presence or absence of substrings of the derivation string. This brings along two further natural parameters to measure descriptional complexity, namely, the maximum permitting string length p and the maximum forbidden string length f, usually summarized as the degree $$d=(p,f)$$ . We show that simple semi-conditional ins–del systems of degree (2, 1) and with ID sizes $$(1+e,e',e'';1+d,d',d'')$$ are computationally complete for any $$e,e',e'',d,d',d''\in \{0,1\}$$ , with $$e+e'+e''=1$$ and $$d+d'+d''=1$$ . The obtained results complement and improve on the existing results known from the literature. To prove our results, we also show a new normal form for type-0 grammars that appears to be interesting in its own right.

This paper investigates the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation and that verbal languages cannot be context-free (unless they are either the empty word or the full group). They can however be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively.

We characterize the recursively enumerable first order Godel logics with △ with respect to validity and non-satisfiability. The finitely valued and four infinitely valued Godel logics with △ are recursively enumerable, not-satisfiability is recursively enumerable if validity is recursively enumerable. This is in contrast to first order Godel logics without △, where validity is recursively enumerable for finitely valued and two infinitely valued Godel logics, not-satisfiability is recursively enumerable if validity is recursively enumerable or 0 isolated in the truth value set.

Insertion-deletion systems have been introduced as a formalism to model operations that find their counterparts in ideas of bio-computing, more specifically, when using DNA or RNA strings and biological mechanisms that work on these strings. So-called matrix control has been introduced to insertion-deletion systems in order to enable writing short program fragments. We discuss substitutions as a further type of operation, added to matrix insertion-deletion systems. For such systems, we additionally discuss the effect of appearance checking. This way, we obtain new characterizations of the family of context-sensitive and the family of recursively enumerable languages. Not much context is needed for systems with appearance checking to reach computational completeness. This also suggests that bio-computers may run rather traditionally written programs, as our simulations also show how Turing machines, like any other computational device, can be simulated by certain matrix insertion-deletion-substitution systems.

In this work, we construct splicing recognizers of radius 2 capable of accepting recursively enumerable languages. Cavaliere, Jonoska and Leupold introduced the concept of splicing recognizers in 2006 and constructed splicing recognizers of radius 4 which can accept recursively enumerable languages. It was conjectured that the radius of splicing recognizers, accepting recursively enumerable languages can be decreased. We prove in this paper that the conjecture is true and in fact, radius 2 is sufficient. We also introduce the concept of time varying splicing recognizers and show that these recognizers of radius 1 are capable of accepting recursively enumerable languages.

We present initial limit Datalog, a new extensible class of constrained Horn clauses for which the satisfiability problem is decidable. The class may be viewed as a generalisation to higher-order logic (with a simple restriction on types) of the first-order language limit Datalog$_Z$ (a fragment of Datalog modulo linear integer arithmetic), but can be instantiated with any suitable background theory. For example, the fragment is decidable over any countable well-quasi-order with a decidable first-order theory, such as natural number vectors under componentwise linear arithmetic, and words of a bounded, context-free language ordered by the subword relation. Formulas of initial limit Datalog have the property that, under some assumptions on the background theory, their satisfiability can be witnessed by a new kind of term model which we call entwined structures. Whilst the set of all models is typically uncountable, the set of all entwined structures is recursively enumerable, and model checking is decidable., Comment: 18 pages. To be published in LICS 2021

Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence relation which partitions the natural numbers into infinitely many equivalence classes. The present work investigates the infinite one-one numbered recursively enumerable (r.e.) families realised by such relations and asks how the choice of the equivalence relation impacts the learnability properties of these classes when studying learnability in the limit from positive examples, also known as learning from text. For all choices of such positive equivalence relations, for each of the following entries, there are one-one numbered r.e. families which satisfy it: (a) they are behaviourally correctly learnable but not vacillatorily learnable; (b) they are explanatorily learnable but not confidently learnable; (c) they are not behaviourally correctly learnable. Furthermore, there is a positive equivalence relation which enforces that (d) every vacillatorily learnable one-one numbered family of languages closed under this equivalence relation is already explanatorily learnable and cannot be confidently learnable.

We show that the logic of partial quasiary predicates is undecidable over arbitrary structures and not recursively enumerable over finite structures. The results are obtained by reduction from the classical predicate logic.

We consider generalized forbidding insertion-deletion systems (GFID) where each insertion-deletion rule is associated with a set \(\mathcal {F}\) of words and the rule can be applied to a string only if every word of \(\mathcal {F}\) is not a subword of the string. The parameters in the size \((k;n,i',i'';m,j',j'')\) of a GFID system denote (from left to right) the maximum length of a word in \(\mathcal {F}\), the maximal length of an insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; the last three parameters follow a similar pattern with respect to deletion. We show that GFID systems of sizes \((k;n,i',i'';m,j',j'')\), where \(k=2\) and \(n\,+\,i'\,+\,i''=m\,+\,j'\,+\,j''=2\), with \(n,m> 0\) and \(i',i'',j',j''\in \{0,1\}\), describe all recursively enumerable languages, by explaining algorithms that transform a given type-0 grammar in some normal form to a GFID system of the required size.

In this paper, we show that pure insertion grammars of size 2 (i.e., inserting two symbols in a left and right context, each consisting of two symbols) can characterize all recursively enumerable languages. This is achieved by either applying an inverse morphism and a weak coding, or a left (right) quotient with a regular L O C ( 2 ) language, or an intersection with a L O C ( 2 ) language and a weak coding. The obtained results improve the descriptional complexity of insertion grammars and complete the picture of known results on insertion-deletion systems that are motivated from the DNA computing area.

With good biological motivation, we add substitutions as a further type of operations to (in particular, context-free) insertion-deletion systems. This way, we obtain new characterizations of and normal forms for context-sensitive and recursively enumerable languages.

Context-sensitive fusion grammars are a special case of context-dependent fusion grammars where a rule has only a single positive context condition instead of finite sets of positive and negative context conditions. They generate hypergraph languages from start hypergraphs via successive applications of context-sensitive fusion rules and multiplications of connected components, as well as a filtering mechanism to extract terminal hypergraphs from derived hypergraphs in a certain way. The application of a context-sensitive fusion rule consumes two complementarily labeled hyperedges and identifies corresponding attachment vertices provided that the context condition holds. In this paper, we show that the Post correspondence problem can be formulated very intuitively by such a grammar. Furthermore, we prove that these grammars can generate all recursively enumerable string languages (up to representation of strings as graphs) and are universal in this respect.

We construct recursively-presented finitely-generated torsion groups which have bounded torsion and whose word problem is conjunctive equivalent (in particular positive and Turing equivalent) to a given recursively enumerable set. These groups can be interpreted as groups of finite state machines or as subgroups of topological full groups, on effective subshifts over other torsion groups. We define a recursion-theoretic property of a set of natural numbers, called impredictability. It roughly states that a Turing machine can enumerate numbers such that every Turing machine occasionally incorrectly guesses (by either halting or not) whether they are in the set, even given an oracle for a prefix of the set. We prove that impredictable recursively enumerable sets exist. Combining these constructions and slightly adapting a result of [Salo and Torma, 2017], we obtain that four-headed group-walking finite-state automata can define strictly more subshifts than three-headed automata on a group containing a copy of the integers, confirming a conjecture of [Salo and Torma, 2017]. These are the first examples of groups where four heads are better than three, and they show the maximal height of a finite head hierarchy is indeed four.

We discuss substitutions as a further type of operations, added to (in particular, one-sided) insertion-deletion systems. This way, we obtain new characterizations of classes of context-sensitive and recursively enumerable languages. Moreover, we obtain new families of languages containing all regular or contained in the context-free languages.

A binary relation on graphs is recursively enumerable if and only if it can be computed by a formula in monadic second-order logic. The latter means that the formula defines a set of graphs, in the usual way, such that each "computation graph" in that set determines a pair consisting of an input graph and an output graph., Comment: 12 pages, 4 figures, to appear in Information Processing Letters

A celebrated result by M. Davis, H. Putnam, J. Robinson, and Y. Matiyasevich shows that a set of integers is listable if and only if it is positive existentially definable in the language of arithmetic. We investigate analogues of this result over structures endowed with a listable presentation. When such an analogue holds, the structure is said to have the DPRM property. We prove several results addressing foundational aspects around this problem, such as uniqueness of the listable presentation, transference of the DPRM property under interpretation, and its relation with positive existential bi-interpretability. A first application of our results is the rigorous proof of (strong versions of) several folklore facts regarding transference of the DPRM property. Another application of the theory we develop is that it will allow us to link various Diophantine conjectures to the question of whether the DPRM property holds for global fields. This last topic includes a study of the number of existential quantifiers needed to define a Diophantine set., Comment: Changes in the introduction and typos corrected

The set of all formulas whose n-provability in a given arithmetical theory S is provable in another arithmetical theory T is a recursively enumerable extension of S. We prove that such extensions can be naturally axiomatized in terms of transfinite progressions of iterated local reflection schemata over S. Specifically, the set of all provably 1-provable sentences in Peano arithmetic PA can be axiomatized by an e0-times iterated local reflection schema over PA. The resulting characterizations provide additional information on the proof-theoretic strength of these theories and on the complexity of their axiomatization.

Generic amplification is a method that allows algebraically undecidable problems to generate problems undecidable for almost all inputs. It is proved that every simple negligible set is undecidable for almost all inputs, but it cannot be obtained via amplification from any undecidable set. On the other hand, it is shown that every recursively enumerable set with nonzero asymptotic density can be obtained via amplification from a set of natural numbers.

OCL is the standard language for defining constraints in UML class diagrams. Unfortunately, as we show in this paper, full OCL is so expressive that it is not possible to check general OCL constraints efficiently. In particular, we show that checking general OCL constraints is not only not polynomial, but not even semidecidable. To overcome this situation, we identify $$\hbox {OCL}_\textsf {FO}$$ , a fragment of OCL which is expressively equivalent to relational algebra (RA). By equivalent we mean that any $$\hbox {OCL}_\textsf {FO}$$ constraint can be checked through a RA query (which guarantees that $$\hbox {OCL}_\textsf {FO}$$ checking is efficient, i.e., polynomial), and any RA query encoding some constraint can be written as an $$\hbox {OCL}_\textsf {FO}$$ constraint (which guarantees expressiveness of $$\hbox {OCL}_\textsf {FO}$$ ). In this paper we define the syntax of $$\hbox {OCL}_\textsf {FO}$$ , we concisely determine its semantics through set theory, and we prove its equivalence to RA. Additionally, we identify the core of this language, i.e., a minimal subset of $$\hbox {OCL}_\textsf {FO}$$ equivalent to RA.

P systems with graph productions were introduced by Freund in 2004. It was shown that such a variant of P system can generate any recursively enumerable language of weakly connected graphs. In this paper, we consider such P systems where the input is any connected graph and each graph production is labelled over an alphabet. We name the system as Process Guided P System where the computation is guided by a string over the set of labels. The set of all strings over the label alphabet which results in the halting computation of the system forms a guiding language of the system. We compare such guiding languages with Chomsky hierarchy. Two direct applications of this variant are also given.

A graph-controlled insertion-deletion (GCID) system has several components and each component contains some insertion-deletion rules. A transition is performed by any applicable rule in the current component on a string and the resultant string is then moved to the target component specified in the rule. The language of the system is the set of all terminal strings collected in the final component. When resources are very limited (especially, when deletion is demanded to be context-free and insertion to be one-sided only), then GCID systems are not known to describe the class of recursively enumerable languages. Hence, it becomes interesting to explore the descriptional complexity of such GCID systems of small sizes with respect to language classes below RE and even below CF. To this end, we consider so-called closure classes of linear languages defined over the operations concatenation, Kleene star and union. We show that whenever GCID systems (with certain syntactical restrictions) describe all linear languages (LIN) with t components, we can extend this to GCID systems with just one more component to describe, for instance, the concatenation of two languages from the language family that can be described as the Kleene closure of linear languages. With further addition of one more component, we can extend the construction to GCID systems that describe the regular closure of LIN.

Nonlinear spiking neural P (NSNP) system is a distributed parallel computing model inspired from the mechanisms of spiking neurons. Computational completeness of NSNP systems as number generating/accepting devices and function computing devices has been already discussed. However, universality result of NSNP systems as language generating devices has not been established so far. This paper investigates computational power of NSNP systems as language generating devices. The relationships of languages generated by NSNP systems with regular languages are investigated. Moreover, we prove that recursively enumerable languages can be characterized by the projection of inverse-morphic images of languages generated by NSNP systems.

Nonconstructive computations by various types of machines and automata have been considered by, for example, Karp and Lipton as well as Freivalds. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. This paper studies the amount of nonconstructivity needed to learn classes of formal languages. Different learning types are compared with respect to the amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data. Matching upper and lower bounds for the amount of nonconstructivity needed are shown. (C) 2020 Elsevier Inc. All rights reserved.