Splicing semigroups of dominoes and DNA
From MaRDI portal
Publication:1175793
DOI10.1016/0166-218X(91)90054-ZzbMath0747.20035MaRDI QIDQ1175793
Publication date: 25 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
stringsregular languagePost correspondence problemalphabetundecidablealphabetic dominoessemigroup of dominoessplicing semigroups
Free semigroups, generators and relations, word problems (20M05) Protein sequences, DNA sequences (92D20) Cellular automata (computational aspects) (68Q80) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (40)
Descriptional Complexity of Semi-simple Splicing Systems ⋮ Accepting splicing systems with permitting and forbidding words ⋮ Computing by splicing ⋮ Constants and label-equivalence: a decision procedure for reflexive regular splicing languages ⋮ Deciding whether a regular language is generated by a splicing system ⋮ Circular splicing and regularity ⋮ Aparallel digraphs and splicing machines ⋮ On the splicing operation ⋮ Regularity of splicing languages ⋮ The finest homophonic partition and related code concepts ⋮ Recognizing splicing languages: syntactic monoids and simultaneous pumping ⋮ Simple splicing systems ⋮ Descriptional Complexity of Semi-Simple Splicing Systems ⋮ On the power of the splicing operation1 ⋮ DESCRIPTIONAL COMPLEXITY OF SPLICING SYSTEMS ⋮ Time and space complexity for splicing systems ⋮ Restricted use of the splicing operation1 ⋮ Finite-state automata in information technologies ⋮ Complexity theory for splicing systems ⋮ A remark on morphic sturmian words ⋮ Splicing systems with targets are computationally universal ⋮ Unnamed Item ⋮ Regular splicing languages and subclasses ⋮ Linear splicing and syntactic monoid ⋮ Accepting splicing systems ⋮ The structure of reflexive regular splicing languages via Schützenberger constants ⋮ Formal properties of PA-matching ⋮ Partial words and a theorem of Fine and Wilf revisited ⋮ DNA Splicing Systems ⋮ Derivation languages and descriptional complexity measures of restricted flat splicing systems ⋮ Splicing Systems: Accepting Versus Generating ⋮ Splicing representations of stricly locally testable languages ⋮ Splicing in abstract families of languages ⋮ DNA computing based on splicing: Universality results ⋮ Frontier between decidability and undecidability: A survey ⋮ On the universality of Post and splicing systems ⋮ Matrix splicing system ⋮ Topics in the theory of DNA computing. ⋮ Conjugacy on partial words. ⋮ Existence of constants in regular splicing languages
Cites Work
This page was built for publication: Splicing semigroups of dominoes and DNA
