On the undecidability and descriptional complexity of synchronized regular expressions

DOI10.1007/S00236-023-00439-3MaRDI QIDQ6171822zbMATH OpenOpenAlexFDO

Authors Jingnan Xie, H. B. III Hunt

Publication date 16 August 2023

Published in Acta Informatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• Bad news on decision problems for patterns
• Characterising REGEX languages by regular languages equipped with factor-referencing
• Computational Parallels between the Regular and Context-Free Languages
• Descriptional complexity -- an introductory survey
• Deterministic regular expressions with back-references
• Extended regular expressions: succinctness and decidability
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3640909 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 2068878 (Why is no real title available?)
• scientific article; zbMATH DE number 3248552 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Inside the class of REGEX languages
• Multi-pattern languages
• On Concatenative Decompositions of Regular Events
• On Equivalence and Containment Problems for Formal Languages
• On Extended Regular Expressions
• On the intersection of regex languages with regular languages
• Permutation automata
• Re-examining regular expressions with backreferences
• Studies in abstract families of languages
• Synchronized regular expressions
• The loop complexity of pure-group events
• Ultimate-Definite and Symmetric-Definite Events and Automata

Cited in

(7)

• Deciding Whether or Not a Synchronous Relation is Regular Prefix
• scientific article; zbMATH DE number 871236 (Why is no real title available?)
• Pumping lemmas can be ``harmful
• Decision problems concerning L systems
• On the computational and descriptional complexity of multi-pattern languages
• A practical extension of computational complexity theory for applications in mathematics and sciences
• Two-way nondeterministic finite automata with quantum and classical states and their limits

This page was built for publication: On the undecidability and descriptional complexity of synchronized regular expressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6171822)