Results 1 to 10 of about 4,373 (234)
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
Turing machines based on unsharp quantum logic [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 In this paper, we consider Turing machines based on unsharp quantum logic. For a lattice-ordered quantum multiple-valued (MV) algebra E, we introduce E-valued non-deterministic Turing machines (ENTMs) and E-valued deterministic Turing machines (EDTMs ...
Yun Shang, Xian Lu, Ruqian Lu
doaj +4 more sources
Existential Definability over the Subword Ordering [PDF]
Logical Methods in Computer Science, 2023 We study first-order logic (FO) over the structure consisting of finite words over some alphabet $A$, together with the (non-contiguous) subword ordering.
Pascal Baumann +3 more
doaj +1 more source
Complete Symmetry in D2L Systems and Cellular Automata [PDF]
, 1985 We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing ...
Asveld, Peter R.J.
core +13 more sources
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
Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
Algorithms, 2021 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.
Martin Vu, Henning Fernau
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
Transformation of Turing Machines into Context-Dependent Fusion Grammars [PDF]
Electronic Proceedings in Theoretical Computer Science, 2019 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 ...
Aaron Lye
doaj +1 more source
Equality sets for recursively enumerable languages [PDF]
RAIRO - Theoretical Informatics and Applications, 2005 We consider shifted equality sets of the form EG(a, g1 ,g 2 )= {w | g1(w )= ag2(w)} ,w hereg1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and EG(J )i s as hifted equality set. We prove several closure properties for this family.
Vesa Halava +3 more
openaire +1 more source