The power of synchronizing operations on strings
From MaRDI portal
Publication:1161057
DOI10.1016/0304-3975(81)90054-2zbMath0477.68034OpenAlexW2092602906MaRDI 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
shufflecancellationrecursively enumerable languagesflow expressionsiterated shuffleevent expressionsinverse shuffleleast full trio
Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25) Recursively (computably) enumerable sets and degrees (03D25)
Related Items
Infinite unfair shuffles and associativity, The Frobenius problem for the shuffle operation, Literal shuffle, Unshuffling a square is NP-hard, The equational theory of pomsets, Jumping Finite Automata: Characterizations and Complexity, Regularity Conditions for Iterated Shuffle on Commutative Regular Languages, Permuting operations on strings and their relation to prime numbers, Infinite hierarchy of shuffle expressions over a finite alphabet, Permuting operations on strings and the distribution of their prime numbers, A P-complete language describable with iterated shuffle, String shuffle: circuits and graphs, Synchronized shuffles, Algèbre de processus et synchronisation, Shuffle languages are in P, Insertion languages, On the complexity of iterated shuffle, Extending regular expressions with iterated shuffle, Another generalization of Higman's well quasi order result on \(\Sigma ^*\), The commutative closure of shuffle languages over group languages is regular, Characterization and complexity results on jumping finite automata
Cites Work
