On the undecidability and descriptional complexity of synchronized regular expressions
Acta Informatica · 2023-09 · 60 (3) · 257-278
DOI: 10.1007/s00236-023-00439-3 ↗Kurz gefasst
Fachartikel in der Zeitschrift Acta Informatica, online erschienen am 10.04.2023. Verfasst von Jingnan Xie und 1 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
In Freydenberger (Theory Comput Syst 53(2):159–193, 2013. https://doi.org/10.1007/s00224-012-9389-0 ), Freydenberger shows that the set of invalid computations of an extended Turing machine can be recognized by a synchronized regular expression [as defined in Della Penna et al. (Acta Informatica 39(1):31–70, 2003. https://doi.org/10.1007/s00236-002-0099-y )]. Therefore, the widely discussed predicate “ $$=\{0,1\}^*$$ = { 0 , 1 } ∗ ” is not recursively enumerable for synchronized regular expressions (SRE). In this paper, we employ a stronger form of non-recursive enumerability called productiveness and show that the set of invalid computations of a deterministic Turing machine on a single input can be recognized by a synchronized regular expression. Hence, for a polynomial-time decidable subset of SRE, where each expression generates either $$\{0, 1\}^*$$ { 0 , 1 } ∗ or $$\{0, 1\}^* -\{w\}$$ { 0 , 1 } ∗ - { w } where $$w \in \{0, 1\}^*$$ w ∈ { 0 , 1 } ∗ , the predicate “ $$=\{0,1\}^*$$ = { 0 , 1 } ∗ ” is productive. This result can be easily applied to other classes of language descriptors due to the simplicity of the construction in its proof. This result also implies that many computational problems, especially promise problems, for SRE are productive. These problems include language class comparison problems (e.g., does a given synchronized regular expression generate a context-free language?), and equivalence and containment problems of several types (e.g., does a given synchronized regular expression generate a language equal to a fixed unbounded regular set?). In addition, we study the descriptional complexity of SRE. A generalized method for studying trade-offs between SRE and many classes of language descriptors is established.
Zitieren
APA
Xie, J., & Hunt, H. B. (2023). On the undecidability and descriptional complexity of synchronized regular expressions. Acta Informatica, 60(3), 257-278. https://doi.org/10.1007/s00236-023-00439-3
Vancouver
Xie J, Hunt HB. On the undecidability and descriptional complexity of synchronized regular expressions. Acta Informatica. 2023;60(3):257-278. doi:10.1007/s00236-023-00439-3
BibTeX
@article{Xie2023,
author = {Xie, Jingnan and Hunt, Harry B.},
title = {On the undecidability and descriptional complexity of synchronized regular expressions},
journal = {Acta Informatica},
year = {2023},
volume = {60},
number = {3},
pages = {257--278},
doi = {10.1007/s00236-023-00439-3}
}
EUVIMED