Shuffle on trajectories: Syntactic constraints

DOI10.1016/S0304-3975(97)00163-1zbMath0902.68096OpenAlexW2089182307MaRDI QIDQ1128661

Alexandru Mateescu, Grzegorz Rozenberg, Arto Salomaa

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00163-1

zbMATH Keywords

shuffleparallel computationformal languagesconcurrency

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

Automatic synthesis of a subclass of schedulers in timed systems., Balanced-by-construction regular and \(\omega \)-regular languages, A loopless algorithm for generating the permutations of a multiset, Infinite unfair shuffles and associativity, FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION, Codes defined by multiple sets of trajectories, Algebraic properties of substitution on trajectories, Deletion along trajectories, Shuffled languages -- representation and recognition, Tree shuffle, Pumping lemmas for classes of languages generated by folding systems, Block insertion and deletion on trajectories, Balanced-by-Construction Regular and ω-Regular Languages, An extension of a Y. C. Yang theorem, A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS, RESTRICTED SETS OF TRAJECTORIES AND DECIDABILITY OF SHUFFLE DECOMPOSITIONS, Bond-free DNA language classes, On Language Decompositions and Primality, Shuffle on Trajectories over Finite Array Languages, PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES, SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES, Aspects of shuffle and deletion on trajectories, Hairpin structures defined by DNA trajectories, On properties of bond-free DNA languages, Language Decompositions, Primality, and Trajectory-Based Operations, State complexity of deletion and bipolar deletion, ORTHOGONAL SHUFFLE ON TRAJECTORIES, OPERATIONS ON TRAJECTORIES WITH APPLICATIONS TO CODING AND BIOINFORMATICS, NOTES ON DUAL CONCATENATION, Language equations, Site-directed insertion: language equations and decision problems, Decidability of trajectory-based equations, Algebraic properties of the shuffle over \(\omega\)-trajectories, Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lie elements and an algebra associated with shuffles
• Theory of traces
• A calculus of communicating systems
• Flatwords and Post Correspondence Problem
• A hierarchy between context-free and context-sensitive languages
• AFL with the semilinear property
• Using string languages to describe picture languages
• Process algebra for synchronous communication
• The Universal Field of Fractions of a Semifir I. Numerators and Denominators
• Process Algebra
• On slender context-free languages
• Distributed catenation and chomsky hierarchy
• Bounded Regular Sets
• On equal matrix languages
• Simple matrix languages
• On free monoids partially ordered by embedding
• Ordering by Divisibility in Abstract Algebras
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)