The power of synchronizing operations on strings
From MaRDI portal
Publication:1161057
DOI10.1016/0304-3975(81)90054-2zbMath0477.68034MaRDI QIDQ1161057
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(81)90054-2
shuffle; cancellation; recursively enumerable languages; flow expressions; iterated shuffle; event expressions; inverse shuffle; least full trio
68Q45: Formal languages and automata
68Q65: Abstract data types; algebraic specification
03B25: Decidability of theories and sets of sentences
03D25: Recursively (computably) enumerable sets and degrees
Related Items
Permuting operations on strings and their relation to prime numbers, Algèbre de processus et synchronisation, Insertion languages, On the complexity of iterated shuffle, Infinite hierarchy of shuffle expressions over a finite alphabet, Extending regular expressions with iterated shuffle, Another generalization of Higman's well quasi order result on \(\Sigma ^*\), Literal shuffle, The equational theory of pomsets, A P-complete language describable with iterated shuffle, Shuffle languages are in P, Infinite unfair shuffles and associativity, Synchronized shuffles
Cites Work