LANGUAGES OF ENCODED LINE PATTERNS

被引：23

作者：

FEDER, J

机构：

[1] Department of Electrical Engineering, New York University, Bronx

来源：

INFORMATION AND CONTROL | 1968年 / 13卷 / 03期

关键词：

D O I：

10.1016/S0019-9958(68)91105-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

By treating patterns as statements in a two-dimensional language, it is possible to apply linguistic theory to pattern analysis and recognition. In this paper, line patterns are encoded into string form using the chain code developed by Freeman. A class of patterns, or pattern language, encodes to a set of strings that is examined using theory that exists for string languages and automata. Pattern languages formed on the basis of equations in two variables and various pattern properties are related to the hierarchy of string language classes. The known relationships between classes of string languages and classes of automata can then be applied to determine bounds on the time and memory required to recognize the various patterns. Results can be extended to other forms of pattern encoding provided that a suitable translator can be constructed. © 1968 Academic Press Inc.

引用

页码：230 / &

共 17 条

[1] BARHILLEL Y, 1960, 4 OFF NAV RES INF SY
[2] Chomsky N., 1963, HDB MATH PSYCHOL, P323
[3] Chomsky N., 1958, INFORM CONTR, V1, P91, DOI DOI 10.1016/S0019-9958(58)90082-2
[4] Chomsky N., 1959, INFORM CONTROL, V2, P137, DOI 10.1016/S0019-9958(59)90362-6
[5] FEDER J, 1966, NYU400147 DEP EL ENG
[6] FEDER J, 1966, NYU400133 DEP EL ENG
[7] FEDER J, 1967, NYU400165 DEP EL ENG
[8] FREEMAN H, 1961, IRE T, VEC10, P260
[9] GLASS JM, 1965, NYU400112 DEP EL ENG
[10] Kleene SC., 1956, Automata Stud, V34, P3

← 1 2 →