TY - JOUR

T1 - Efficient automaton-based recognition for linear conjunctive languages

AU - Okhotin, Alexander

PY - 2003/12/1

Y1 - 2003/12/1

N2 - Linear conjunctive grammars have recently been proved computationally equivalent to triangular trellis automata. The relation between these grammars and these automata resembles that between regular expressions and finite automata: while the former are better suited for human use, the latter are considerably easier to implement. This paper studies efficient algorithms for converting a linear conjunctive grammar to an equivalent triangular trellis automaton, and also proposes a number of techniques of reducing the size of these automata.

AB - Linear conjunctive grammars have recently been proved computationally equivalent to triangular trellis automata. The relation between these grammars and these automata resembles that between regular expressions and finite automata: while the former are better suited for human use, the latter are considerably easier to implement. This paper studies efficient algorithms for converting a linear conjunctive grammar to an equivalent triangular trellis automaton, and also proposes a number of techniques of reducing the size of these automata.

KW - cellular automata

KW - Conjunctive grammars

KW - recognition

KW - trellis automata

UR - http://www.scopus.com/inward/record.url?scp=47849099967&partnerID=8YFLogxK

U2 - 10.1142/S0129054103002205

DO - 10.1142/S0129054103002205

M3 - Article

AN - SCOPUS:47849099967

VL - 14

SP - 1103

EP - 1116

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 6

ER -