On the undecidability and descriptional complexity of synchronized regular expressions

DOI10.1007/s00236-023-00439-3OpenAlexW4363678954MaRDI QIDQ6171822

Jingnan Xie, Harry B. III Hunt

Publication date: 16 August 2023

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-023-00439-3

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extended regular expressions: succinctness and decidability
• Multi-pattern languages
• On the intersection of regex languages with regular languages
• Bad news on decision problems for patterns
• Synchronized regular expressions
• Deterministic regular expressions with back-references
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Re-examining regular expressions with backreferences
• On Extended Regular Expressions
• On Equivalence and Containment Problems for Formal Languages
• Computational Parallels between the Regular and Context-Free Languages
• Ultimate-Definite and Symmetric-Definite Events and Automata
• INSIDE THE CLASS OF REGEX LANGUAGES
• On Concatenative Decompositions of Regular Events
• Permutation automata
• The loop complexity of pure-group events
• Studies in abstract families of languages
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS