Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication [PDF]
Electronic Proceedings in Theoretical Computer Science, 2010 Starting from the fact that complete Accepting Hybrid Networks of Evolutionary Processors allow much communication between the nodes and are far from network structures used in practice, we propose in this paper three network topologies that restrict the
Jürgen Dassow, Florin Manea
doaj +4 more sources
On the Size Complexity of Non-Returning Context-Free PC Grammar Systems [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 Improving the previously known best bound, we show that any recursively enumerable language can be generated with a non-returning parallel communicating (PC) grammar system having six context-free components.
Erzsébet Csuhaj-Varjú, György Vaszil
doaj +6 more sources
Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during
Tomáš Masopust, Alexander Meduna
doaj +4 more sources
Representing recursively enumerable languages by iterated deletion
Theoretical Computer Science, 2004 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Michael Domaratzki, Alexander Okhotin
exaly +3 more sources
A homomorphic characterization of recursively enumerable languages
Theoretical Computer Science, 1985 We give a homomorphic characterization of the class of recursively enumerable languages: it is shown that any recursively enumerable language is the homomorphic image of the intersection of a Dyck language and a 'minimal linear' language.
Sadaki Hirose
exaly +2 more sources
Homomorphic characterizations of recursively enumerable languages with very small language classes
Theoretical Computer Science, 2001 In this paper, we attempt to characterize the class of recursively enumerable languages with much smaller language classes than that of linear languages. Language classes, \((i,j)\) LL and \((i,j)ML,\) of \((i,j)\) linear languages and \((i,j)\) minimal linear languages are defined by posing restrictions on the form of production rules and the number ...
Sadaki Hirose
exaly +2 more sources
Hilbert's Tenth Problem in Coq (Extended Version) [PDF]
Logical Methods in Computer Science, 2022 We formalise the undecidability of solvability of Diophantine equations, i.e. polynomial equations over natural numbers, in Coq's constructive type theory.
Dominique Larchey-Wendling +1 more
doaj +1 more source
Computational Power of P Systems with Small Size Insertion and Deletion Rules [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 Recent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages.
Sergey Verlan +2 more
doaj +1 more source
On Parsing Programming Languages with Turing-Complete Parser
Mathematics, 2023 A new parsing method based on the semi-Thue system is described. Similar to, but with more efficient implementation than Markov normal algorithms, it can be used for parsing any recursively enumerable language.
Boštjan Slivnik, Marjan Mernik
doaj +1 more source
Partial Learning of Recursively Enumerable Languages [PDF]
Theoretical Computer Science, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ziyuan Gao +2 more
openaire +2 more sources