The power of synchronizing operations on strings

DOI10.1016/0304-3975(81)90054-2zbMath0477.68034MaRDI 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

shuffle; cancellation; recursively enumerable languages; flow expressions; iterated shuffle; event expressions; inverse shuffle; least full trio

Mathematics Subject Classification ID

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, String shuffle: circuits and graphs, Infinite unfair shuffles and associativity, Permuting operations on strings and the distribution of their prime numbers, Synchronized shuffles, Unshuffling a square is NP-hard, Jumping Finite Automata: Characterizations and Complexity

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