The power of synchronizing operations on strings

DOI10.1016/0304-3975(81)90054-2zbMath0477.68034OpenAlexW2092602906MaRDI QIDQ1161057

Matthias Jantzen

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

zbMATH Keywords

shufflecancellationrecursively enumerable languagesflow expressionsiterated shuffleevent expressionsinverse shuffleleast full trio

Mathematics Subject Classification ID

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

• Remarks on blind and partially blind one-way multicounter machines
• Software Descriptions with Flow Expressions
• An approach to software system modelling and analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item