구조화된 예측에서의 주요 과제 중 하나는 출력 구조 내의 상호의존성(Interdependencies)을 적절히 표현하는 것이다. 출력이 시계열 구조로 구성될 경우, 선형 체인 조건부 확률 필드(Linear-chain Conditional Random Fields, CRFs)는 출력 내의 국소적 의존성(Local dependencies)을 학습할 수 있는 널리 사용되는 모델 클래스이다. 그러나 CRF의 마르코프 가정(Markov assumption)은 비국소적 의존성(Nonlocal dependencies)을 갖는 분포를 표현할 수 없게 하며, 표준 CRF는 데이터의 비국소적 제약(예: 출력 레이블에 대한 전역적인 아리티 제약(Global arity constraints))을 만족시킬 수 없다. 본 논문에서는 가능한 출력 구조의 공간을 정규 언어(Regular language) $\mathcal{L}$로 지정함으로써, 비국소적 제약을 포함한 광범위한 종류의 제약을 강제할 수 있는 CRF의 일반화된 모델을 제안한다. 이를 통해 도출된 정규 언어 제약 CRF(Regular-constrained CRF, RegCCRF)는 표준 CRF와 동일한 수학적 성질을 가지되, $\mathcal{L}$에 속하지 않는 모든 레이블 시퀀스에 대해 확률을 0으로 부여한다. 특히, RegCCRF는 관련된 모델들이 추론(decoding) 단계에서만 제약을 강제하는 것과 달리, 학습 과정에서 제약을 직접 통합할 수 있다. 우리는 제약을 학습 단계에서 적용하는 것이 추론 단계에서 제약을 적용하는 것보다 항상 우수하거나 동등함을 증명하였으며, 실증적으로는 실제로 훨씬 더 우수한 성능을 보임을 보였다. 또한, 심층 신경망 기반의 의미 역할 명명(Semantic Role Labeling) 모델에 RegCCRF를 통합함으로써 하류 작업에서 실용적인 성능 향상을 입증하였으며, 표준 데이터셋에서 기존 최고 성능(SOTA)을 초과하는 결과를 달성하였다.