Strict Local Testability: a Linguistic Model for Syntactical Analysis

Antonio Magnaghi and Hidehiko Tanaka
The University of Tokyo
window from the left to the right end of the string.
Every time the window is slid right-ward by one letter,
Local Testability (LT ) is an active area of research in y is incorrect if the visible substring is not contained
the eld of formal languages. It is a fruitful concept either in 3 (if it is the pre x) or in 3 (if it is a properin describing di erent phenomena that extend to vari- substring) or in 3 (if it is the sux). On the otherous contexts and situations. On an abstract level, LT hand, when such a test produces a positive result on
expresses the possibility to ascertain the value of an all 3-substrings and the right end of y is reached, thenattribute of a complex instance from a class of objects the sentence is recognized as an element of L.
through the analysis of simple constituents of the in- The example above clari es the basic ideas underlying
stance itself, without requiring to consider the whole the concept of LT s:s: Our interest in the property ofobject at once. The interest in LT goes beyond formal local testability bases on its link to the linguistic unilanguages: it can be applied, for instance, to pattern versal of Aperiodicity. Formally, the class of Aperiodic
recognition, parallel parsing, error recovery, neural net- languages is generated by the closure of LT s:s: classworks, symbolic logic and algebraic structures [2, 4]. In w.r.t. boolean operators and concatenation. Aperiodthe following sections we will pinpoint some consider- icity expresses the property that the language de niations about LT in a strict sense (LTs:s:): it identi- tion is free from constraints counting modulo an integer
es a subclass of the class LT . Firstly, the paper will over any sentence constituents. Such a characteristic
outline some results we could achieve on LT s:s: reg- is empirically met by all natural languages as well asular languages. Then, preliminary considerations will arti cial ones. It is known that, instead, aperiodic lanbe examined about our intent to generalize the mathe- guages can easily be algorithmically inferred [3]. Hencematical framework and decidibility results to tree lan- LT s:s: constitutes a relevant linguistic model for synguages.
tactical analysis. A systematic characterization of locally testable languages was presented in the past [2].
2 String LT s:s: and language parsing
This section focuses on k-local testability in a strict However, the adopted techniques relied on the study ofsense (LT s:s:) for string languages. Moreover it un- the algebraic structure of the syntactic monoid. Therederlines the links of this class of languages to the lin- fore the conceptual framework results elaborate andguistic property of Aperiodicity, directly providing mo- computational problems were left unresolved.
tivations to a further investigation about the more gen- 3 New Results on Stringseral case of tree languages.
We tried to frame the concept of LTs:s: in an original
Based on [4], for every integer k a language L on the combinatoric perspective. Our approach aimed at capalphabet 6 is LT s:s: if sets ; ;  6 exist such turing strict local testability in a direct manner, withthat:out employing any algebraic property of the syntactic
8x 2 63 ; x 2 L ()monoid.
Instead, a set-theoretically based analysis isL (x) 2 ^ I (x)  ^ R (x) 2(1)carried out in order to link local testability to topologIn (1) L (x) is the k-pre x of x, R is the k-sux and ical properties of the automaton of language L. TheI (x) is the set of proper substrings of x.
speci c points we addressed can be summarized as folFor instance, let us consider the regular language L lows:over the alphabet 6 = fa; bg, whose strings are such 1. Characterization of LT s:s: property: for a speci cthat the occurrence of symbol a implies the occurinteger value of k, the analyzed decision problem
rence of the substring abb: L = fx : x = uav )is: \L 2 LT s:s:?"v = bbw; 8a 2 x; w 2 63 g. L 2 LT3 s:s: because,A sucient and necessary condition is formulated.
simply by a decomposition of an arbitrary string y in
It involves topological properties of paths in theits 3-substrings, it is possible to locally analyze theaccepting automaton. Such a characterization has
string and evaluate whether it meets the syntactical
the advantage to impose determinism as a uniqueconstraint de ning L. Let 3 = fabb; bab; bba; bbbg,constraint, without requiring the automaton to be
3 = 3 , 3 = fabb; bbbg denote respectively the setsreduced. Nonetheless the minimal automaton caseof all 3-pre xes, 3-internal-substrings, 3-suxes of senis studied and then conveniently employed in subtences belonging to the language. Such string collecsequent considerations.
tions represent the repository of recognition patterns
to utilize when y is parsed. The correctness of y can 2. Development of an algorithm to decide LT s:s:
be evaluated moving a 3-letter-wide one-dimension
property (existential problem): given language L,
1 Introduction

kkkkkkkkkkkkkkkkk

1

does a value of k exist such that L 2 LT s:s:?
from the axiom: in this case E and T . Let s be theOur approach consists, rst, in de ning the Pre x- skeleton associated to sentence x. s can be decomposedPath-Intersection Graph (PPIG). For its construc- in depth-2 trees belonging to 2 and 2 ensuring thattion a xed-point algorithm is formulated. Then it is syntactically correct.
its complexity is shown to be o(j6j2 mn), where Let L be a tree language, a set of k-pre x recog6; m and n are, respectively, the alphabet of L, nition trees, and a set of k-internal/k-frontier recogthe number of edges and the number of states of nition trees. We propose the following de nition. L isin LT s:s: w.r.t. ; i :the nite state automaton accepting L.
8 tree t : t 2 L () pre (t) 2^ int (t) (2)3. Development of an algorithm for the optimizaIn (2) the operator pre (t) produces the k-depth subtion problem of order evaluation: for a language
tree
rooted in the root of t and the operator int (t)L 2 LT s:s:, which is the minimum value kproduces
the set of k-depth subtrees of t whose root issuch that k = min fk : L 2 LT s:s:g?
at depth level one at least. The introduced de nition
The study of the PPIG properties relates the tries to extend LT s:s: property from linear sequences
length of the longest path in the PPIG to the or- of symbols to more articulated structures with a topoder of language L. Then, nally, we obtained the logical asset. The developed model shows a remarkablemajor result: the order of L can be evaluated in property concerning grammatical inference. Through ao(j6j2mn).
convenient labeling procedure of the nodes of elements
In addition to previous results, the introduced ap- in ; , it is possible to infer a generative contextproach seems to have a worthwhile characteristic: the free grammar whose skeleton language coincides withsyntactic monoid and its algebraic structure are not in- the language de ned by (2). In addition, the analysis ofvolved. This leads us to think that such an approach such and algorithm reveals that LT s:s: tree languages
might e ectively give insights on how to extend our are accepted by deterministic top-down tree automata.
considerations to di erent contexts, where linear se- On the other hand it is known that a non-deterministic
quences of symbols are replace by more complex lin- top-down tree automaton is required for the generalguistic structures. Therefore we are now investigating case of an arbitrary context-free grammar. This showsthat our de nition is a re nement compared to type 2
on tree languages.
grammars. Hence, such a characteristic constitutes a
4 Preliminary results on Tree Languages
preliminary supporting result to the aim of capturing
The representative power of regular languages does not peculiar linguistic aspect of LT .
allow to describe important linguistic aspects. Hence 5 Future Research Activity
programming languages are always de ned throughcontext-free grammars (type 2 in Chomsky's classi - Future research activity will elaborate a proper mathcation [1]) and during parsing activity the input pro- ematical framework for tree languages in order to adgram is represented, internally to the compiler, by dress problems of LT s:s: decidibility and order evaluaan abstract syntax tree. However context-free gram- tion. In particular, as an applied aspect, software tools
mars are capable to describe also counting phenomena, will be implemented for testing the soundness of theowhich are never present in linguistic communication retical considerations w.r.t. the syntax of programming
processes. Therefore this kind of formalism appears languages.
to be excessively general. We aim at investigating the References
adequacy of LTs:s: on trees as a linguistic model to [1] A. Aho, J. Ullman. The Theory of Parsing, Transdescribe syntactical aspects. Let us consider the gramlation, and Compiling. Volume 1, Addison-Wesley,
mar G and the sentence x = a + a + a 3 a.
1974
G:E -> E + T | T[2] J. A. Brzozowski. Hierarchies of aperiodic lanT -> T * F | Fguages. R.A.I.R.O. Information Theorique (vol.
F -> a10, No. 8, ao^ut 1976, pp. 33-49)
G de nes arithmetic expressions in two operators ofdi erent precedence. The skeleton language S (G) of [3] S. Crespi-Reghizzi, M. A. Melkano , L. Lichten.
The use of grammatical inference for designing
G is the set of all derivation trees T (G) of sentences
programming languages. Comm. ACM 16, 2 (Feb.
of G where non-terminals have been deleted from in1973), pp. 83-90
ternal nodes. Intuitively the tree language S (G) is 2strictly locally testable in the sense that every skeleton [4] R. McNaughton, S. Papert. Counter-free aucan be parsed by elements belonging to convenient sets
tomata. M.I.T. Press, Cambridge, MA, 1971
2 ; 2 . 2 contains all possible depth-2 pre x recognition skeletons generated from the axiom of G, and 2 [5] M. Steinby. A theory of language varieties. in Treeconsists of depth-2 internal/frontier recognition skeleAutomata and Languages, M. Nivat and A. Podeltons that can be generated by non-terminals reachableski (editors), Elsevier Publ., 1992, pp. 57-81
kkkkkkkkkkkkminminkkkk