Seminar

Wednesday, 29 January 2025, Aula C

11:00

Pietro Sala (Università di Verona)

Concatenation is All You Need (to avoid!)

The emptiness problem for generalized regular expressions has been extensively studied, with the seminal work of Stockmeyer establishing non-elementary lower bounds for the case of expressions without the Kleene star operator [1]. This complexity result has profound connections to temporal logic, specifically through the relationship between language concatenation and the chop modality in interval temporal logic under homogeneity assumptions [2]. In this talk, we investigate an alternative formulation where we replace the binary concatenation operator with two unary operators: prefix (begins) and suffix (ends) [3]. We examine how this modification affects the computational complexity of the emptiness problem, providing insights into the structural properties that contribute to the complexity of the problem. Our analysis sheds new light on how various combinations of operators affect the computational complexity of decision problems for regular languages.

[1] Larry Joseph Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Massachusetts Institute of Technology, 1974. URL: http://hdl.handle.net/1721. 1/15540.

[2] Joseph Halpern, Zohar Manna, and Ben Moszkowski. A hardware semantics based on temporal intervals. In Josep Diaz, editor, Automata, Languages and Programming, pages 278-291, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg. doi: 10.1007/BFB0036915.

[3] Dario Della Monica, Angelo Montanari, Gabriele Puppis, and Pietro Sala. The Logic of Prefixes and Suffixes is Elementary under Homogeneity. LICS 2023: 1-12