complete

美國政府 NLRB 給出競業及禁止挖角條款違法的判決

在「NLRB judge declares non-compete clause is an unfair labor practice (nlrbedge.com)」這邊看到的，原始文章是：「In First Case of its Kind, NLRB Judge Declares Non-Compete Clause Is an Unfair Labor Practice」。

NLRB (National Labor Relations Board) 這次是針對 J.O. Mory 的判決，原始判決本來想連結到 NLRB 的網站上，但發現現在連不上，先給這份好了：「09031d4583d765f7.pdf」。

裡面有兩個面向的判決，一個是競業的部分，另外一個是禁挖的部分。細節可以直接看原文，或是直接丟 Google Translate 或是叫 ChatGPT & Gemini 翻譯都可以。

競業條款的部分不算太意外，因為整個州政府與聯邦政府都在修法大幅限制企業在合約上面可以設定的競業條款，不再讓自由市場機制決定勞工的工作權益 (通常是弱勢方)。

禁挖條款的部分是這次看到覺得比較新鮮的，認定違法的原因與禁業的部分類似，都是以會影響勞工的工作權益而宣告違法。

這塊應該是進行式，這幾年應該還是可以看到不同的判決出現...

Perl 的 Regular Expression 的強度：NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目，就像是維基百科上的條列：

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇，裡面試著用 Perl 的 regular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。

Recursive descent parser 可以當作是 CFG 的子集合，而 CFG 對應到的語言是 CFL，另外他對應到的自動機是 PDA。

我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern)，所以他能接受的 language 已經超過 RL，但我很好奇他能夠做到什麼程度。

用搜尋引擎翻了翻，查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library)：「Which languages do Perl-compatible regular expressions recognize?」。

在裡面有人提到「The true power of regular expressions」這篇文章，裡面給了一個在 PTIME 演算法，將 3SAT 轉換到 PCRE 裡解，這證明了 PCRE 是 NP-hard；另外也很容易確認 PCRE 是 NP，所以就達成了 NP-complete 的條件了...

本來一直以為 PCRE 只是 CFG/CFL/PDA 而已，沒想到這麼強，NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD