정규 언어의 유도

Induction of regular languages

계산 학습 이론에서 정규 언어의 유도는 주어진 예시 문자열 집합으로부터 정규 언어의 형식적 설명(예: 문법)을 배우는 과제를 말한다.비록 E. Mark Gold가 모든 정규 언어가 이런 식으로 학습될 수 있는 것은 아니라는 것을 보여주었지만(한계의 언어 식별 참조), 다양한 하위 클래스에 대한 접근법은 조사되어 왔다.그들은 이 글에 스케치되어 있다.일반적인 문법에 대한 자세한 내용은 문법 유도를 참조하십시오.

예

정규어는 "완료 자동"이나 "정규 문법" 또는 "정규 표현"이라고 불리는 수학적 형식 중 하나로 설명할 수 있는 (완료 또는 무한) 문자열 집합으로 정의되는데, 모두 같은 표현력을 가지고 있다.후자의 형식주의는 최단 기호로 이어지기 때문에 여기에 도입하여 사용해야 한다.기호(예: 알파벳)의 σ 집합에 따라 정규식은 다음 중 어느 것이 될 수 있다.

  • ∅ (빈 문자열 집합을 나타냄)
  • ε (빈 문자열만 포함된 싱글톤 세트를 나타냄)
  • a (여기서 a는 σ에서 임의의 문자, 단일 문자 문자열 a를 포함하는 싱글톤 집합을 나타냄)
  • r+(r과 s가 차례로 단순한 정규 표현식인 경우, 집합의 조합을 나타냄)
  • r⋅s(r 및 s 집합에서 가능한 모든 문자열 연결 집합을 나타냄)
  • r+(n-fold 반복 집합의 rs 집합에서 n-fold 반복을 나타냄, 임의의 n-fold1에 대해) 또는
  • r* (n-폴드 반복의 집합을 나타내며, 0-폴드 반복으로 보이는 빈 문자열도 포함한다.)

예를 들어 σ = { 0.1 }을(를) 사용하는 정규식(0+1+1+1)⋅(0+1)은 1자리 또는 2자리 숫자(선행 0 허용)를 가진 모든 이진수 집합을 나타내고, 1㎛(0+*1)10은 모든 짝수 이진수(선행 0)의 (무한) 집합을 나타낸다.

문자열 집합("긍정적인 예"라고도 함)을 주어, 규칙적인 언어 유도의 과제는 그 모든 것을 포함하는 집합을 나타내는 규칙적인 표현을 생각해 내는 것이다.예를 들어, {1, 10, 100 }을(를) 주어진 경우, "자연적" 설명은 정규식 1 00일* 수 있는데, 이는 비공식적 특성화 "1 뒤에 임의적으로 많은 (아마도 없는) 0이 뒤따른다"에 해당된다.그러나 (0+1)*과 1+(1⋅0)+(1⋅0⋅0)는 또 하나의 정규식으로서, 주어진 문자열을 포함하는 가장 큰( (={0,1})과 가장 작은 집합을 나타내며, 각각 사소한 과일반화와 과소일반화라고 부른다.일부 접근방식은 확장된 환경에서 작동하며, 여기서 "부정적 예" 문자열의 집합도 제공된다. 그런 다음, 모든 양의 예시를 생성하는 정규식을 찾되, 부정적인 예시는 전혀 발견되지 않는다.

오토마타 격자

문자열 1, 10 및 100을 생성하는 자동 데이터의 부분 순서(양수 예제)음의 각 예시 문자열 11, 1001, 101, 0에 대해, 이를 생성하는 오토마타의 상위 집합이 표시된다.{1, 10, 100 }을(를) 모두 생성하는 유일한 오토마타지만, { 11, 1001, 101, 0 } 중 어느 것도 하찮은 하부 오토마톤이며 정규식 1⋅0에* 해당하는 오토마타는 아니다.

듀퐁 외주어진 예제 문자열의 입력 세트를 생성하는 구조적으로 완전한 모든 유한 자동화의[note 1] 집합이 격자를 형성하며, 사소한 부분적인 부분적인 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적 부분적이 격자의 각 구성원은 적절한 동등성 관계에 의해 저일반화된 자동화를 인수하여 얻을 수 있다.

위의 예시 문자열 세트 {1, 10, 100 }의 경우 그림 하단에 상태 a, b, c, d로 구성된 미일반화된 자동 Aa,b,c,d(회색)가 표시된다.상태 집합 { a,b,c,d }에는 총 15개의 동등성 관계가 존재하며 격자를 형성한다.각 동등성 E를 해당 지수 자동 언어 L(Aa,b,c,d / E)에 매핑하면[note 2] 그림에 표시된 부분 순서의 집합을 얻는다.각 노드의 언어는 정규식으로 표시된다.언어는 지수 자동자 w.r.t. 상이한 동등성 관계에 의해 인식될 수 있으며, 이 모든 것은 노드 아래에 표시된다.두 노드 사이의 화살표는 하위 노드의 언어가 상위 노드의 적절한 하위 집합임을 나타낸다.

만약 긍정적인 예시 문자열과 부정적인 예시 문자열이 모두 주어진다면, 듀폰트 등은 긍정적인 예시로부터 격자를 만든 다음, 부정적인 예시를 생성하는 오토마타와 그렇지 않은 오토마타 사이의 분리 경계를 조사한다.가장 흥미로운 것은 국경 바로 아래에 있는 오토마타 입니다.[1]그림에서 분리 경계는 음의 예시 문자열 11(녹색), 1001(파란), 101(시안), 0(빨간색)에 대해 표시된다.

코스트와 니콜라스는 격자 안에서 독자적인 검색 방법을 제시하는데, 이는 미첼의 버전 우주 패러다임과 관련이 있다.분리 경계를 찾기 위해, 그들은 부정적인 예에 의해 유도된 주 불평등 관계에 대한 그래프 색칠 알고리즘을 사용한다.[2]나중에, 그들은 가능한 모든 국가 유착의 집합에 대해 몇 가지 주문 관계를 조사한다.[3]

쿠도와 심보는 자동 인자화에 의한 표현을 사용하여 다음과 같은 접근법에 대한 고유한 프레임워크를 제공한다(아래에 표시).

이러한 각각의 접근방식은 인자화에 사용되는 특정한 종류의 동등성 관계에 해당한다고 보여진다.[5]

접근

k자형 언어

앵글루인은 소위 "k-역전 가능한" 정규 오토마타, 즉 길이 k의 전환 사슬을 따라 각 상태가 최대 한 주에서 도달할 수 있는 결정론적 오토마타를 고려한다.Formally, if Σ, Q, and δ denote the input alphabet, the state set, and the transition function of an automaton A, respectively, then A is called k-reversible if : ∀a0,...,ak ∈ Σ ∀s1, s2 ∈ Q: δ*(s1,a0...ak) = δ*(s2,a0...ak) ⇒ s1 = s2, where δ* means the homomorphic extension of δ to arbitrary words.앙글루인은 주어진 입력 단어의 집합으로부터 가장 작은 k-반복 가능한 언어의 학습을 위한 입방 알고리즘을 제공한다; k=0의 경우 알고리즘은 거의 선형 복잡성을 가진다.[6][7]기호가 부여된 k+1 이후의 필수 상태 고유성은 자동 상태를 통일하게 하여 사소한 미개념 자동화와 다른 적절한 일반화를 초래한다.이 알고리즘은 영어 구문의 간단한 부분을 배우기 위해 사용되어왔다;[8] 나중에 증분 버전이 제공되었다.[9]k-역전성 자동화에 기초한 또 다른 접근방식은 꼬리 군집화 방법이다.[10]

후계자 오토마타

주어진 입력 문자열 집합에서 베르나닷과 리체틴은 각각의 구별되는 문자에 대해 하나의 상태와 각각의 인접한 두 문자 상태 사이의 전환으로 구성된 소위 후계자 자동화를 구축한다.[11]예를 들어 싱글톤 입력 세트 { aabbaabb }은 정규식(a+⋅b+)에 해당하는 자동화를 유도한다.*

이 접근방식의 확장은 각 문자 반복을 즉시 클라인으로 일반화한 다음 각 문자마다 해당 주의 가능한 이전 문자 집합을 포함하는 선행 처리 방식이다.후계자 오토마타는 현지 언어의 클래스를 정확히 배울 수 있다.각 정규 언어는 지역 언어의 동형상이기 때문에 적절한 (용도에 따라 달라짐) 동형상(homomorphism)이 제공될 경우, 전 계층의 그래머는 리프팅을 통해 학습할 수 있다.특히 전임자-서커스 방식에서 학습할 수 있는 언어의 클래스에 대해서는 그러한 동형성이 있다.[12]현지 언어의 학습능력은 k-반복 가능한 언어의 학습능력으로 감소할 수 있다.[13][14]

"con"과 관련하여 사전 문자열 집합의 Brzozowski 파생 모델(빨간색 배경)
일반 오토마타용 펌핑 보조정리 그림

초기 접근법

촘스키와 밀러(1957년)[15]하고 automaton에 배울에 상응하는 사이클 구축하려고 노력은 입력 uvw 문자열의 한 부분 v 같아요;그들이 줄이 uw 적절한 k, uvvw, uvvvw,...을 요구하면 회원 가입 쿼리를 사용한 펌프 부명제 사용, uvkw 또한 중국어를 하여의 구조를 보고 배울 것이다. 그들의오토매틱의1959년에 솔로몬노프는 맥락이 없는 언어에 대한 이 접근법을 일반화했는데, 이것은 또한 펌프질 보조정리법을 따른다.[16]

커버오토마타

쿰페아누 외큰 유한 언어의 콤팩트한 표현으로 유한 자동화를 배우다.그러한 언어 F를 주어, 그들은 L(A)의 언어 L(A≤l)이 F를 포괄하는 이른바 커버 오토메이션 A를 검색한다: L(A) ∩ ∩ = = F, 여기서 l는 F에서 가장 긴 문자열의 길이, σ는≤l l보다 길지 않은 모든 문자열의 집합을 나타낸다.그러한 커버 자동화가 존재하는 경우, F는 A와 l에 의해 고유하게 결정된다.예를 들어 F = { ad, read, read }에는 l=6이 있고 정규식(r⋅e)⋅*a⋅d에 해당하는 표지 자동이 있다.

두 문자열 x와 y의 경우 xz와 yz가 모두 l보다 길지 않도록 길이의 모든 문자열 z에 대해 xz∈F ⇔ yz∈F인 경우 x ~ y를 정의한다.[17]이러한 관계에 기초하여, Transitability의[note 3] 부족이 상당한 기술적 문제를 야기하는, 그들은 최소 상태 카운트의 커버 오토메이션 A를 F로부터 구성할 수 있는 O4([note 4]n) 알고리즘을 부여한다.더욱이, 조합, 교차로 및 두 개의 유한한 언어의 차이에 대해서는 커버 오토마타에 해당하는 연산을 제공한다.[18][19]Păun 등은 시간 복잡성을 O(n2)로 개선한다.[20]

잔존오토마타

문자열의 S 세트와 문자열 u의 경우, Brzozowski 파생 모델 U.는−1 접두사 u(가능한 경우)를 잘라내 S의 문자열에서 얻을 수 있는 모든 휴식 스트링 집합으로 정의된다. 공식−1: U = { v ∈ σ* σ: uv ∈ S}, cf. 그림.[21]Denis 외.는 잔류 자동화를 각 상태 q가 승인된 언어 L(A)의 Brzozowski 파생상품에 해당하는 비계수적 유한 자동화 A로 정의한다. 여기서 ∀q ∃u*∈: L(A,q) = uL−1(A), 여기서 L(A,q)은 q에서 시작 상태로 승인된 언어를 나타낸다.

그것들은 각각의 정규 언어가 고유하게 결정된 최소 잔류 자동화에 의해 생성된다는 것을 보여준다.그것의 주(州)는 ∪-불가포함 브조조스키 파생상품이며, 최소 결정론적 자동화에 비해 기하급수적으로 작을 수 있다.게다가, 그들은 정규 언어에 대한 잔여 오토마타는 최적의 샘플 입력을 가정하더라도 다항식 시간에는 학습할 수 없다는 것을 보여준다.그들은 잔여 자동화에 대한 학습 알고리즘을 제공하고 그것이 양과 음의 입력 문자열의 특징적인 샘플로부터 자동화를 학습한다는 것을 증명한다.[22][23]

학습 쿼리

정규 언어는 다항 시간에는 멤버십 쿼리만[24] 사용하거나 동등성 쿼리만 사용하여 학습할 수 없다.[25]그러나 앙글루인은 회원 쿼리와 동등성 쿼리를 이용해 다항식 시간에 정규 언어를 학습할 수 있음을 보여주었고, 이를 정확히 하는 학습 알고리즘 L*을 제공했다.[26]L* 알고리즘은 나중에 NL*[27]이라는 알고리즘을 통해 DFA(결정론적 유한 오토마타)가 아닌 NFA(비결정적 유한 오토마타)를 출력하도록 일반화되었다.이 결과는 더욱 일반화되었고, AL*이라고 불리는 AFA(대체 유한 자동자)를 출력하는 알고리즘이 고안되었다.[28]NFA는 DFA보다 기하급수적으로 더 간명할 수 있고, AFA는 NFA보다 기하급수적으로 간명할 수 있으며, 두 배로 더 간명할 수 있다는 점에 주목한다.[29]

정규식 감소

브릴은 감소된 정규 표현을 정의한다.

  • a (여기서 a는 σ에서 임의의 문자, 단일 문자 문자열 a를 포함하는 싱글톤 집합을 나타냄)
  • ¬a (a를 제외한 σ의 다른 단일 문자를 나타냄)
  • • (EX에서 단일 문자를 나타냄)
  • a*, (¬a)* 또는 *• (각각 a, ¬a 또는 •의 집합에서 문자 반복, 0을 임의로 나타냄) 또는
  • r⋅s (r과 s가 차례로 더 단순하게 축소된 정규식; r과 s 집합에서 가능한 모든 문자열 연결의 집합을 나타냄)

입력 문자열 집합에 따라, 그는 각 분기에 일부 입력 문자열의 접두사를 허용하는 축소된 정규식으로 라벨을 표시하고, 각 노드에 허용되는 접두사 길이 집합으로 라벨을 붙인 트리를 단계별로 구축한다.그는 언어 수업의 학습 가능성에 대한 이론적 고려보다는 영어 [note 5]철자 오류에 대한 수정 규칙을 배우는 것을 목표로 한다.그 결과, 그는 휴리스틱스를 사용하여 나무 덤핑을 가지런히 제거하여 런타임의 상당한 개선을 이끈다.[30]

적용들

메모들

  1. ^ 즉, 문자열의 지정된 입력 집합과 관련하여 불필요한 상태 및 전환이 없는 유한한 자동 데이터
  2. ^ 이 지도는 격자 동형성이 아니라 단조적 지도일 뿐이다.
  3. ^ 예를 들어, F = {aab, baa, aabb }은(는) aab ~ aabb(이것을 확인하려면 z=ba(이러한 경우)와 aabb ~ baa(유사한 경우 z=b로 인한 경우)로 이어진다.Campeanu 등에 따르면.(2001, Leemma 1, p.5) 그러나 x ~ y ~ z → x ~ z 문자열은 x ~ y ~ z를 유지한다.
  4. ^ 여기서 n은 L(AF) = F와 같은 DFA A의F 상태 수입니다.
  5. ^ 예를 들어, "(과거) 컨텍스트에서 "통과"로 "과거"를 대체하십시오.*COULTER_NUNounpast"

참조

  1. ^ P. Dupont; L. Miclet; E. Vidal (1994). "What is the Search Space of the Regular Inference?". In R. C. Carrasco; J. Oncina (eds.). Proceedings of the Second International Colloquium on Grammatical Inference (ICGI): Grammatical Inference and Applications. LNCS. Vol. 862. Springer. pp. 25–37. CiteSeerX 10.1.1.54.5734.
  2. ^ F. Coste; J. Nicolas (1997). "Regular Inference as a Graph Coloring Problem". Proc. ICML Workshop on Grammatical Inference, Automata Induction, and Language Acquisition. pp. 9–7. CiteSeerX 10.1.1.34.4048.
  3. ^ F. Coste; J. Nicolas (1998). "How Considering Incompatible State Mergings May Reduce the DFA Induction Search Tree". In Vasant Honavar; Giora Slutzki (eds.). Grammatical Inference, 4th International Colloquium, ICGI. LNCS. Vol. 1433. Springer. pp. 199–210. CiteSeerX 10.1.1.34.2050.
  4. ^ Dominique Luzeaux (Aug 1997). "A Universal Approach to Positive Regular Grammar Inference". Proc. 15th World IMACS Congress on Scientific Computation, Modelling and Applied Mathematics.
  5. ^ M. Kudo; M. Shimbo (1988). "Efficient Regular Grammatical Inference Techniques by the Use of Partial Similarities and Their Logical Relationships". Pattern Recognition. 21 (4): 401–409. Bibcode:1988PatRe..21..401K. doi:10.1016/0031-3203(88)90053-2.
  6. ^ D. Angluin (1981). "A Note on the Number of Queries Needed to Identify Regular Languages". Information and Control. 51: 76–87. doi:10.1016/s0019-9958(81)90090-5.
  7. ^ D. Angluin (1982). "Inference of Reversible Languages". J. ACM. 293 (3): 741–765. CiteSeerX 10.1.1.232.8749. doi:10.1145/322326.322334. S2CID 18300595.
  8. ^ Robert C. Berwick; Samuel F. Pilato (1987). "Learning Syntax by Automata Induction". Machine Learning. 2 (1): 9–38. doi:10.1007/bf00058753.
  9. ^ Rajesh Parekh; Codrin Nichitiu; Vasant Honavar (Jan 1997). A Polynomial Time Incremental Algorithm for Regular Grammar Inference (Technical report). AI Research Group, Iowa State Univ. p. 14. TR 97-03.
  10. ^ L. Miclet; C. Faure (1985). Reconnaissance des Formes Structurelle: Développement et Tendances (Technical report). INRIA.
  11. ^ F. Vernadat; M. Richetin (1984). "Regular Inference for Syntactic Pattern Recognition: A Case Study". Proc. 7th International Conference on Pattern Recognition (ICPR). pp. 1370–1372.
  12. ^ P. Garcia; E. Vidal; F. Casacuberta (1987). "Local Languages, The Successor Method, and a Step Towards a General Methodology for the Inference of Regular Grammars". IEEE Transactions on Pattern Analysis and Machine Intelligence. 9.
  13. ^ Takashi Yokomori (Oct 1989). "Learning Context-Free Languages Efficiently". In K.P. Jantke (ed.). Proc. Int. Workshop AII. LNAI. Vol. 397. Springer. pp. 104–123. doi:10.1007/3-540-51734-0_54. ISBN 978-3-540-51734-4.
  14. ^ Satoshi Kobayashi; Takashi Yokomori (1994). "Learning Concatenations of Locally Testable Languages from Positive Data". In Setsuo Arikawa; Klaus P. Jantke (eds.). Proc. 5th ALT. LNAI. Vol. 872. Springer. pp. 405–422. CiteSeerX 10.1.1.52.4678.
  15. ^ N. Chomsky; G.A. Miller (1957). Pattern Conception (Technical report). ASTIA. Document AD110076.
  16. ^ R. Solomonoff (Jun 1959). "A New Method for Discovering the Grammars of Phrase Structure Languages". Proc. Int. Conf. on Information Processing. R.Oldenbourg. pp. 285–290.
  17. ^ 이 관계는 Myhill-Nerode 정리로부터 R 관계를F 일반화한다.그것은 다음의 3장에서 더 자세히 조사되었다.
  18. ^ a b Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (1998). "Minimal Cover-Automata for Finite Languages". In J.-M. Champarnaud; D. Maurel; D. Ziadi (eds.). Proc. Workshop on Implementing Automata (WIA) (PDF). LNCS. Vol. 1660. Springer. pp. 43–56. CiteSeerX 10.1.1.37.431. doi:10.1007/3-540-48057-9_4. ISBN 978-3-540-66652-3.
  19. ^ Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (2001). "Minimal Cover-Automata for Finite Languages". Theoretical Computer Science. 267 (1–2): 3–16. doi:10.1016/s0304-3975(00)00292-9.
  20. ^ Andrei Păun; Nicolae Sântean; Sheng Yu (Sep 2001). "An O(n2) Algorithm for Constructing Minimal Cover Automata for Finite Languages". In Sheng Yu; Andrei Păun (eds.). Proc. 5th Int. Conf. on Implementation and Application of Automata (CIAA) (PDF). LNCS. Vol. 2088. Springer. pp. 243–251. ISBN 978-3-540-42491-8.
  21. ^ Janusz A. Brzozowski (1964). "Derivatives of Regular Expressions". J ACM. 11 (4): 481–494. doi:10.1145/321239.321249. S2CID 14126942.
  22. ^ François Denis; Aurélien Lemay; Alain Terlutte (2000). "Learning Regular Languages Using Non Deterministic Finite Automata". In Arlindo L. Oliveira (ed.). Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI. LNCS. Vol. 1891. Springer. pp. 39–50. CiteSeerX 10.1.1.13.5559. ISBN 978-3-540-41011-9.
  23. ^ François Denis; Aurélien Lemay; Alain Terlutte (2001). "Learning Regular Languages using RFSA" (PDF). Proc. ALT '01.
  24. ^ Angluin, Dana (1995). "When Won't Membership Queries Help? (Extended Abstract)". 23rd Annual ACM Symposium on Theory of Computing. Stoc '91: 444–454. doi:10.1145/103418.103420. ISBN 9780897913973. S2CID 9960280.
  25. ^ Angluin, Dana (1990). "Negative Results for Equivalence Queries". Machine Learning. 5 (2): 121–150. doi:10.1007/BF00116034. S2CID 189902172.
  26. ^ Angluin, Dana (1987). "Learning Regular Sets from Queries and Counterexamples". Information and Computation. 75 (2): 87–106. doi:10.1016/0890-5401(87)90052-6.
  27. ^ Bollig; Habermehl; Kern; Leucker (2009). "Angluin-Style Learning of NFA" (PDF). 21st International Joint Conference on Artificial Intelligence.
  28. ^ Angluin; Eisenstat; Fisman (2015). "Learning Regular Languages via Alternating Automata". 24th International Joint Conference on Artificial Intelligence.
  29. ^ Mayer, A.R.; Stockmeyer, Larry J. (1995). "The Complexity of Word Problems - This Time with Interleaving". Information and Computation. 115.
  30. ^ a b Eric Brill (2000). "Pattern–Based Disambiguation for Natural Language Processing" (PDF). Proc. EMNLP/VLC.
  31. ^ Alvis Brazma; Inge Jonassen; Jaak Vilo; Esko Ukkonen (1998). "Pattern Discovery in Biosequences". In Vasant Honavar; Giora Slutzki (eds.). Grammatical Inference, 4th International Colloquium, ICGI. LNCS. Vol. 1433. Springer. pp. 257–270.
  32. ^ M.S. Waterman, ed. (Jan 1989). Mathematical Methods for DNA Sequences. CRC Press. ISBN 978-0849366642.
  33. ^ Fernando Pereira; Yves Schabes (1992). "Inside-Outside Reestimation for partially Bracketed Corpora". Proc. 30th Ann. Meeting of the Assoc. for Comp. Linguistics. pp. 128–135. doi:10.3115/981967.981984. S2CID 63967455.
  34. ^ Helena Ahonen (Nov 1996). Generating Grammars for Structured Documents Using Grammatical Inference Methods (PDF) (Ph.D.). Report. Vol. A-1996-4. University of Helsinki, Department of Computer Science. S2CID 60722498. Archived from the original (PDF) on 2020-02-12.
  35. ^ Stephen Watkinson (1997). Induction of Musical Syntax (Master). Dept. of AI, Univ. Edinburgh. Archived from the original on June 4, 2001.
  36. ^ Pedro P. Cruz-Alcázar; Enrique Vidal (1998). "Learning Regular Grammars to Model Musical Style: Comparing Different Coding Schemes" (PDF). In Vasant Honavar; Giora Slutzki (eds.). Grammatical Inference, 4th International Colloquium, ICGI. LNCS. Vol. 1433. Springer. pp. 211–222. doi:10.1007/BFb0054077. ISBN 978-3-540-64776-8. Archived from the original (PDF) on 2018-02-16.
  37. ^ Alexander S. Saidi; Souad Tayeb-bey (1998). "Grammatical Inference in Document Recognition". In Vasant Honavar; Giora Slutzki (eds.). Grammatical Inference, 4th International Colloquium, ICGI. LNCS. Vol. 1433. Springer. pp. 175–186. ISBN 978-3-540-64776-8.