Closure properties of pattern languages

作者：

Highlights：

• The terminal-free pattern languages are not closed under most standard operations.

• We achieve even stronger results for union and intersection of these languages.

• Some of these results cease to hold if patterns with terminal symbols are considered.

• We characterise unions of two NE-pattern languages that are an E-pattern language.

• We characterise all unions of E-pattern languages that are an NE-pattern language.

摘要

•The terminal-free pattern languages are not closed under most standard operations.•We achieve even stronger results for union and intersection of these languages.•Some of these results cease to hold if patterns with terminal symbols are considered.•We characterise unions of two NE-pattern languages that are an E-pattern language.•We characterise all unions of E-pattern languages that are an NE-pattern language.

论文关键词：Pattern languages,Closure properties

论文评审过程：Received 10 March 2015, Revised 26 May 2016, Accepted 7 July 2016, Available online 2 August 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.07.003