=Paper=
{{Paper
|id=Vol-3226/paper13
|storemode=property
|title=On Pumping RP-automata Controlled by Complete LRG(\cent,$)-grammars
|pdfUrl=https://ceur-ws.org/Vol-3226/paper13.pdf
|volume=Vol-3226
|authors=Martin Plátek,František Mráz,Dana Pardubská,Daniel Průša
|dblpUrl=https://dblp.org/rec/conf/itat/PlatekMPP22
}}
==On Pumping RP-automata Controlled by Complete LRG(\cent,$)-grammars==
https://ceur-ws.org/Vol-3226/paper13.pdf
On Pumping RP-automata Controlled by Complete
LR(¢,$)-grammars
Martin Plátek1 , František Mráz1 , Dana Pardubská2 and Daniel Průša3
1
Charles University, Department of Computer Science, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
2
Comenius University in Bratislava, Department of Computer Science, Mlynská Dolina, 84248 Bratislava, Slovakia
3
Czech Technical University, Department of Cybernetics, Karlovo nám. 13, 121 35 Praha 2, Czech Republic
Abstract
We introduce complete LR(0)-grammars with sentinels (called complete LR(¢,$)-grammars) to prepare tools for the study of
pumping restarting automata controlled by this type of grammars. A complete LR(¢,$)-grammar generates both a language
and the complement of the language with sentinels. Based on a complete LR(¢,$)-grammar, we can construct a deterministic
pumping restarting automaton performing pumping analysis by reduction on each word over its input alphabet. A pumping
reduction analysis is a method where an input word is stepwise simplified by removing at most two continuous parts of the
current word in a way that preserves (in)correctness of the word. Each such simplification corresponds to removing parts of
the current word that could be “pumped” in the sense of a pumping lemma for context-free languages. The computation of a
pumping restarting automaton ends when the original word is shortened under a given length, and then it is decided about
the correctness or incorrectness of the original input word. This means that pumping restarting automata can analyze both
correct and incorrect inputs with respect to a deterministic context-free language (DCFL). That gives an excellent formal
basis for the error localization and the error recovery of DCFL.
Keywords
restarting automata, LR(0)-grammars, complete grammars, Deterministic Context-Free Languages
1. Introduction accepted. Each reduction must be error preserving, i.e., no
word outside the target language can be rewritten into a
This paper aims to enhance and refine results from pa- word from the language.
pers [1, 2] where some distinguishing restrictions for In this paper, we are interested in a stronger version
deterministic monotone restarting pumping automata of reduction analysis called pumping reduction analysis.
(det-mon-RP-automata) were introduced and studied. Pumping reduction analysis is a reduction analysis that
Some linguistic and non-linguistic motivations for this has several additional properties. In each step of pumping
paper can be found already in [1, 2]. Here we work mainly reduction analysis, the current word is not rewritten.
with a motivation to develop formal tools supporting the Instead, at most two continuous segments of the current
characterization and localization of syntactic errors in word are deleted. Further, pumping reduction analysis
deterministic context-free languages. works according to a so-called complete grammar.
Reduction analysis is a method for checking the cor- Informally, a complete grammar (with sentinels ¢ and
rectness of an input word by stepwise rewriting some $) 𝐺𝐶 is an extended context-free grammar that has two
part of the current form with a shorter one until we obtain initial nonterminals 𝑆𝐴 and 𝑆𝑅 . Such grammar has a
a simple word for which we can decide its correctness finite alphabet Σ of terminals not containing ¢ and $,
easily. In general, reduction analysis is nondeterministic, finite alphabet of nonterminals and a set of rewriting
and in one step, we can rewrite a substring of a length rules of the form 𝑋 → 𝛼, where 𝑋 is a nonterminal and
limited by a constant with a shorter string. An input 𝛼 is a string of terminals, nonterminals and sentinels ¢,
word is accepted if there is a sequence of reductions such $. The language generated by the grammar is the set
that the final simple word is from the language. Then, 𝐿 of words 𝑤 such that the word {¢} · 𝑤 · {$} can be
intermediate words obtained during the analysis are also derived from the initial nonterminal 𝑆𝐴 and the set of
ITAT’22: Information technologies – Applications and Theory, Septem- words derived from the second initial nonterminal 𝑆𝑅 is
ber 23–27, 2022, Zuberec, Slovakia exactly {¢} · (Σ* ∖ 𝐿) · {$}.
$ martin.platek@mff.cuni.cz (M. Plátek); Pumping reduction analysis corresponds to a complete
frantisek.mraz@mff.cuni.cz (F. Mráz); grammar 𝐺𝐶 when for each pair of terminal words 𝑢,
pardubska@dcs.fmph.uniba.sk (D. Pardubská); prusa@fel.cvut.cz
𝑣 such that 𝑢 can be reduced to 𝑣, it holds that there
(D. Průša)
0000-0003-3147-6442 (M. Plátek); 0000-0001-9869-3340 (F. Mráz); are some terminal words 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , and a nonter-
0000-0001-9383-8117 (D. Pardubská); 0000-0003-4866-5709 minal 𝐴 such that 𝑢 = 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 , 𝑣 = 𝑥1 𝑥3 𝑥5 , and
(D. Průša) 𝑆 ⇒*𝐺𝐶 𝑥1 𝐴𝑥5 ⇒*𝐺𝐶 𝑥1 𝑥2 𝐴𝑥4 𝑥5 ⇒*𝐺𝐶 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 ,
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0). where 𝑆 equals 𝑆𝐴 or 𝑆𝑅 . Additionally, there exists a
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
constant 𝑐 that depends only on the grammar 𝐺𝐶 such rest of the tape if the tape contents is shorter than 𝑘).
that each word of length at least 𝑐 can be reduced to a The computation of 𝑀 is controlled by the transition
shorter word. function
The main result of the paper is that for each determin- 𝛿 : (𝑄 ∖ (𝑄A ∪ 𝑄R )) × 𝒫𝒞 (𝑘) →
istic context-free language, there exists a complete gram- 𝒫(𝑄 × {MVR, PREPARE }) ∪
mar 𝐺𝐶 and a deterministic restarting RP-automaton 𝑀 𝒫((𝑄A ∪ 𝑄R ) × {HALT }) ∪
that performs pumping reduction analysis on any input {RESTART (𝑣) | 𝑣 ∈ 𝒫𝒞 ≤(𝑘−1) }.
word 𝑤. The last phase of the computation of 𝑀 on 𝑤
will produce a terminal word 𝑤′ that is not longer than Here 𝒫(𝑆) denotes the powerset of the set 𝑆, 𝒫𝒞 (𝑘)
the constant 𝑐. If ¢𝑤′ $ is generated from 𝑆𝐴 according is the set of possible contents of the read/write window
to 𝐺𝐶 , then 𝑤′ (and thus also 𝑤) is accepted by 𝑀 . Oth- of 𝑀 , where for 𝑖, 𝑛 ≥ 0
erwise, if ¢𝑤′ $ is generated from 𝑆𝑅 according to 𝐺𝐶 , 𝒫𝒞 (𝑖) = ({¢} · Σ𝑖−1 ) ∪ Σ𝑖 ∪ (Σ≤𝑖−1 · {$}) ∪
then 𝑤′ (and thus also 𝑤) is rejected by 𝑀 . ({¢} · Σ≤𝑖−2 · {$}),
𝑛 𝑘−1
The paper is structured as follows. Section 2 introduces Σ≤𝑛 =
⋃︀
Σ𝑖 and 𝒫𝒞 ≤(𝑘−1) =
⋃︀
𝒫𝒞 (𝑖) .
RP-automata and LR(0)-grammars, and presents their ba- 𝑖=0 𝑖=0
sic properties. LR(0)-grammars are used for constructing The transition function 𝛿 represents a finite set of
a complete grammar for any deterministic context-free four different types of instructions (transition steps). Let
language. 𝑞, 𝑞 ′ , 𝑞𝐼 be states from 𝑄, 𝑢 ∈ 𝒫𝒞 (𝑘) , 𝑤 ∈ 𝒫𝒞 ≤(𝑘) ,
Section 3 introduces complete grammars and presents 𝑣 ∈ 𝒫𝒞 ≤(𝑘−1) and 𝑀 be in state 𝑞 with 𝑢 being the
a method for constructing a complete grammar for any contents of its read/write window:
given deterministic context-free language. (1) A move-right instruction of the form (𝑞, 𝑢) →𝛿
Section 4 presents the main results of this paper. Here, (𝑞 ′ , MVR) is applicable if 𝑢 ∈ / Σ* $. It causes 𝑀 to enter
we show that for any complete grammar 𝐺𝐶 constructed the state 𝑞 and to move its read/write head one item to
′
in Section 3, we can construct a deterministic restarting the right.
RP-automaton that performs pumping reduction analysis (2) A preparing instruction of the form (𝑞, 𝑢) →𝛿
according to 𝐺𝐶 for any input word. (𝑞𝐼 , PREPARE ) changes 𝑀 ’s state to a restarting state
Finally, Section 5 summarizes the results of the paper 𝑞𝐼 that determines the next instruction, which must be a
and gives an outlook for future research. restarting instruction.
(3) A restarting instruction is of the form (𝑞𝐼 , 𝑤) →𝛿
RESTART (𝑣), where |𝑣| < |𝑤| and if 𝑤 contains any
2. Basic notions sentinel, 𝑣 contains the corresponding sentinels, too. This
instruction is applicable if 𝑤 is a prefix of the contents
At first, we introduce our base automata model called of the read/write window. When executed, 𝑀 replaces
RP-automata. RP-automata are restarting automata [2] 𝑤 with 𝑣 (with this, it shortens its tape) and restarts –
that differ only slightly from the original RW-automata i.e. it enters the initial state and places the window at
introduced in [3]. the leftmost position so that the first item in the win-
An RP-restarting automaton, or an RP-automaton, dow contains ¢. Note that the state 𝑞𝐼 unambiguously
𝑀 = (𝑄, Σ, ¢, $, 𝑞0 , 𝑘, 𝛿, 𝑄A , 𝑄R ) (with 𝑘-bounded gives the pair (𝑤, 𝑣). We can assume that all pairs (𝑤, 𝑣)
lookahead) is a device with a finite state control unit where |𝑤| > |𝑣| and the word 𝑤 can be replaced with 𝑣
with the finite set of states 𝑄 containing two disjunctive by some RESTART instruction are ordered and that 𝐼
subsets 𝑄A , 𝑄R of accepting and rejecting states, respec- is the index of (𝑤, 𝑣) in that sequence. Thus, although
tively. The automaton is equipped with a head moving the RP-automaton is generally nondeterministic, each
on a finite linear flexible tape of items (cells). The first RESTART instruction of 𝑀 corresponds unambigu-
item of the tape always contains the left sentinel sym- ously to one restart state 𝑞𝐼 .
bol ¢, the last one the right sentinel symbol $, and each (4) A halting instruction of the form (𝑞, 𝑢) →𝛿
other item contains a symbol from a finite alphabet Σ (𝑞 ′ , HALT ), where 𝑞 ′ ∈ 𝑄A or 𝑞 ′ ∈ 𝑄R , finishes the
(not containing ¢, $). The head has a flexible read/write computation and causes 𝑀 to accept or reject, respec-
window of length at most 𝑘 (for some 𝑘 ≥ 1) – 𝑀 scans tively, the input word.
𝑘 consecutive items or the rest of the tape when the dis- Thus, the set of states can be divided into three groups –
tance to the right sentinel $ is less than 𝑘. We say that the halting states 𝑄A ∪ 𝑄R , the restarting states (involved
𝑀 is of window size 𝑘. In the initial configuration on an on the left-hand side of restarting instructions), and the
input word 𝑤 ∈ Σ* , the tape contains the input word rest, called the transition states.
delimited by the sentinels ¢ and $, the control unit is in A configuration of an RP-automaton 𝑀 is a word
the initial state 𝑞0 , and the window scans the left sentinel 𝛼𝑞𝛽, where 𝑞 ∈ 𝑄, and either 𝛼 = 𝜆, where 𝜆 denotes
¢ and the first 𝑘 − 1 symbols of the input word (or the the empty word, and 𝛽 ∈ {¢} · Σ* · {$} or 𝛼 ∈ {¢} ·
Σ* and 𝛽 ∈ Σ* · {$}; here 𝑞 represents the current item scanned by a restarting instruction in a cycle is not
state, 𝛼𝛽 is the current contents of the tape, and it is increasing during the whole computation. It means that
understood that the read/write window contains the first during any computation of a monotone RP-automaton
𝑘 symbols of 𝛽 or all symbols of 𝛽 if |𝛽| < 𝑘. An initial the rightmost scanned items by restarting operations do
(restarting) configuration is 𝑞0 ¢𝑤$, where 𝑤 ∈ Σ* . A not increase their distances from the right sentinel $.
rewriting configuration is of the form 𝛼𝑞𝐼 𝛽, where 𝑞𝐼 is Considering a deterministic RP-automaton
a restarting state. 𝑀 = (𝑄, Σ, ¢, $, 𝑞0 , 𝑘, 𝛿, 𝑄A , 𝑄R ), it is for us conve-
A computation of 𝑀 is a sequence 𝐶 = 𝐶0 , 𝐶1 , . . . , nient to suppose it to be in the strong cyclic form; it
𝐶𝑗 of configurations of 𝑀 , where 𝐶0 is a restarting con- means that the words of length less than 𝑘, 𝑘 being the
figuration, 𝐶ℓ+1 is obtained from 𝐶ℓ by a step of 𝑀 , for length of its read/write window, are immediately (hence
all ℓ, 0 ≤ ℓ < 𝑗, denoted as 𝐶ℓ ⊢𝑀 𝐶ℓ+1 , and ⊢*𝑀 is the in a tail) accepted or rejected, and that 𝑀 performs at
reflexive and transitive closure of the single-step relation least one cycle (at least one restarting) on any longer
⊢𝑀 . word. For each RP-automaton 𝑀 , we can construct an
In general, an RP-automaton can be nondeterministic, RP-automaton 𝑀 ′ in strong cyclic form accepting the
i.e. there can be two or more instructions with the same same language as 𝑀 but possibly with greater size of
left-hand side. If that is not the case, the automaton the read/write window [4].
is deterministic. In what follows, we are interested in We use the following obvious notation. RP denotes
deterministic RP-automata, denoted det-RP. the class of all (nondeterministic) RP-automata. Prefix
An input word w is accepted by 𝑀 if there is a com- det- denotes the deterministic version, similarly mon-
putation that starts in the initial configuration with 𝑤 the monotone version. Prefix scf- denotes the version
(bounded by sentinels ¢, $) on the tape and finishes in in the strong cyclic form. ℒ(𝐴), where 𝐴 is some class
an accepting configuration where the control unit is in of automata, denotes the class of languages accepted by
one of the accepting states. 𝐿(𝑀 ) denotes the language automata from 𝐴. E.g., the class of languages accepted
consisting of all words accepted by 𝑀 ; we say that 𝑀 by deterministic monotone RP-automata is denoted by
accepts the language 𝐿(𝑀 ). ℒ(det-mon-RP).
Let 𝑀 be deterministic. 𝐿𝑅 (𝑀 ) denotes the language Since all computations of RP-automata are finite and
consisting of all words rejected by 𝑀 ; we say that 𝑀 the correctness preserving property holds for all deter-
rejects the language 𝐿𝑅 (𝑀 ). ministic RP-automata, the following proposition is obvi-
Restarting steps divide any computation of an RP- ous.
automaton into certain phases that all start in the initial
state in restarting configurations with the read/write Proposition 2. The classes ℒ(det-mon-RP) and
window in the leftmost position. In a phase called cycle, ℒ(det-RP) are closed under complement.
the head moves to the right along the input list (with its Definition 3. Let 𝑀 = (𝑄, Σ, ¢, $, 𝑞0 , 𝑘, 𝛿, 𝑄A , 𝑄R ) be
read/write window) until a restart occurs – in that case, a det-RP-automaton and 𝑢 ∈ Σ* .
the computation is resumed in the initial configuration on Let AR(𝑀, 𝑢) = (𝑢, 𝑢1 , 𝑢2 , · · · , 𝑢𝑛 ), where 𝑢 ⇒𝑀
the new, shorter word. The phase from the last restart to 𝑢1 ⇒𝑀 𝑢2 ⇒𝑀 · · · ⇒𝑀 𝑢𝑛 , and 𝑢𝑛 cannot be reduced
the halting configuration is called tail. This immediately by 𝑀 . We say that AR(𝑀, 𝑢) is the analysis by reduction
implies that any computation of any RP-automaton is of 𝑢 by 𝑀 .
finite (ending in a halting state). Let AR(𝑀 ) = {AR(𝑀, 𝑢)|𝑢 ∈ Σ* }. We say that
The next proposition expresses a certain lucidness of AR(𝑀 ) is analysis by reduction by 𝑀 .
computations of deterministic RP-automata. The no- Let AR(A, 𝑀 ) = {AR(𝑀, 𝑢)|𝑢 ∈ 𝐿(𝑀 )}. We say
tation 𝑢 ⇒𝑀 𝑣 means that there exists a cycle of 𝑀 that AR(A, 𝑀 ) is accepting analysis by reduction by 𝑀 .
starting in the initial configuration with the word 𝑢 on Let AR(R, 𝑀 ) = {AR(𝑀, 𝑢)|𝑢 ∈ 𝐿𝑅 (𝑀 )}. We say
its tape and finishing in the initial configuration with the that AR(R, 𝑀 ) is rejecting analysis by reduction by 𝑀 .
word 𝑣 on its tape; the relation ⇒*𝑀 is the reflexive and
transitive closure of ⇒𝑀 . We say that 𝑀 reduces 𝑢 to 𝑣
if 𝑢 ⇒𝑀 𝑣. 2.1. LR(0) grammars
The validity of the following proposition is obvious. The proof of our main result is strongly based on the
theory of LR(0) grammars. We will recall the definition
Proposition 1. (Correctness preserving property.)
and properties of LR(0) grammars from Harrison [5]. In
Let 𝑀 be a deterministic RP-automaton and 𝑢 ⇒𝑀 𝑣 for
*
contrast to Harrison, we will use the following notation
some words 𝑢, 𝑣. Then 𝑢 ∈ 𝐿(𝑀 ) iff 𝑣 ∈ 𝐿(𝑀 ).
for context-free grammar 𝐺 = (𝑁, Σ, 𝑆, 𝑅), where 𝑁
By a monotone RP-automaton, we mean an RP- is a set of nonterminals, Σ is a set of terminals, 𝑆 ∈ 𝑁
automaton where the following holds for all computa- is the initial symbol and 𝑅 is a finite set of rules of the
tions: the number of items to the right from the rightmost form 𝑋 → 𝛼, for 𝑋 ∈ 𝑁 and 𝛼 ∈ (𝑁 ∪ Σ)* . We use
a common notation ⇒𝑅 for a right derivation rewriting stored at the bottom of the pushdown. Let 𝑧 ∈ Σ* denote
step according to 𝐺. For two words 𝑤, 𝑤′ ∈ (𝑁 ∪ Σ)* , the unread part of the input, and 𝛾𝜏 , where 𝛾 ∈ 𝒯 * and
𝑢 ⇒𝑅 𝑣, if there exist words 𝛼, 𝛽 ∈ (𝑁 ∪ Σ)* , 𝑤 ∈ Σ* 𝜏 ∈ 𝒯 , is the contents of the pushdown. Then, the parser
and nonterminal 𝑋 ∈ 𝑁 such that 𝑢 = 𝛼𝑋𝑤, 𝑣 = 𝛼𝛽𝑤 performs repeatedly the following actions:
and 𝑋 → 𝛽 is a rule from 𝑅. The reflexive and transitive
1. If 𝑓 (𝜏 ) = 𝑠ℎ𝑖𝑓 𝑡, then
closure of the relation ⇒𝑅 we denote as ⇒*𝑅 .
a) if 𝑧 = 𝜆, then the parser 𝑃 outputs an
Definition 4 ([5]). Let 𝐺 = (𝑁, Σ, 𝑆, 𝑅) be a context- error and rejects the input word,
free grammar and 𝛾 ∈ (𝑁 ∪ Σ)* . A handle of 𝛾 is an b) if 𝑧 = 𝑎𝑧 ′ , for some 𝑎 ∈ Σ and 𝑧 ′ ∈ Σ* ,
ordered pair (𝑟, 𝑖), 𝑟 ∈ 𝑅, 𝑖 ≥ 0 such that there exists then
𝐴 ∈ 𝑁, 𝛼, 𝛽 ∈ (𝑁 ∪ Σ)* and 𝑤 ∈ Σ* such that i. if 𝑔(𝜏, 𝑎) = 𝑒𝑟𝑟𝑜𝑟, then the parser
𝑃 outputs an error and rejects the
(a) 𝑆 ⇒*𝑅 𝛼𝐴𝑤 ⇒𝑅 𝛼𝛽𝑤 = 𝛾, input word,
(b) 𝑟 = 𝐴 → 𝛽, and ii. if 𝑔(𝜏, 𝑎) ̸= 𝑒𝑟𝑟𝑜𝑟, then the parser
(c) 𝑖 = |𝛼𝛽|. 𝑃 pushes 𝑎 and 𝑔(𝜏, 𝑎) onto its push-
down.
In general, the identification of a handle in a string is
not uniquely defined, which is not true for LR(0) gram- 2. If 𝑓 (𝜏 ) = 𝑟𝑒𝑑𝑢𝑐𝑒 𝜋, where 𝜋 is a rule 𝐴 → 𝛽
mars. from 𝑅, then 𝑃 pops 2|𝛽| symbols from the push-
down and outputs the rule 𝜋. Let 𝜏 ′ be the table
Definition 5. Let 𝐺 = (𝑁, Σ, 𝑆, 𝑅) be a reduced context- that is uncovered at the top of the pushdown.
free grammar such that 𝑆 ⇒+ 𝑅 𝑆 is not possible in 𝐺. We a) If 𝜏 ′ = 𝜏0 , 𝐴 = 𝑆, and 𝑧 = 𝜆, then the
say 𝐺 is an 𝐿𝑅(0) grammar if, for each 𝑤, 𝑤′ , 𝑥 ∈ Σ* , parser accepts. The output is the reversed
𝜂, 𝛼, 𝛼′ , 𝛽, 𝛽 ′ ∈ (𝑁 ∪ Σ)* , and 𝐴, 𝐴′ ∈ 𝑁 , sequence of rules that, starting from the
initial nonterminal 𝑆, when applied itera-
(a) 𝑆 ⇒*𝑅 𝛼𝐴𝑤 ⇒𝑅 𝛼𝛽𝑤 = 𝜂𝑤 tively on the rightmost nonterminal in the
(b) 𝑆 ⇒*𝑅 𝛼′ 𝐴′ 𝑥 ⇒𝑅 𝛼′ 𝛽 ′ 𝑥 = 𝜂𝑤′ current word from (𝑁 ∪ Σ)* , produces the
implies (𝐴 → 𝛽, |𝛼𝛽|) = (𝐴′ → 𝛽 ′ , |𝛼′ 𝛽 ′ |). input 𝑤.
b) If 𝑔(𝜏 ′ , 𝐴) = 𝑒𝑟𝑟𝑜𝑟, then the parser 𝑃 out-
Note that as a consequence of the above definition we puts an error and rejects the input word.
have that 𝐴 = 𝐴′ , 𝛽 = 𝛽 ′ , 𝛼 = 𝛼′ , 𝜂 = 𝛼𝛽 = 𝛼′ 𝛽 ′ c) Otherwise, 𝑃 pushes 𝐴 and 𝑔(𝜏 ′ , 𝐴) onto
and 𝑥 = 𝑤′ . Thus, if 𝐺 is an LR(0) grammar, then the its pushdown.
rightmost derivation of the word 𝑤 by 𝐺 and the left-
In what follows, we will refer to an LR(0) analyzer as
right analysis is unique (deterministic). In this paper, we
a pushdown automaton. Based on the way how it is con-
consider 𝐿𝑅(0) grammars rather as analytical grammars.
structed, the pushdown automaton has several properties
A language generated by an LR(0) grammar is called an
that are essential for our constructions below:
LR(0) language.
In [5], there is shown that every LR(0) language is • The pushdown automaton is deterministic.
deterministic context-free, and for each deterministic • If a word 𝑤 is accepted by 𝑃 , then the output of
context-free language 𝐿 ⊆ Σ* and symbol $ ̸∈ Σ, the 𝑃 corresponds to a unique derivation tree.
language 𝐿 · {$} is LR(0). Further, the monograph de- • Let at some step of the computation of 𝑃 on
scribes how to construct an “LR-style parser”. Let us input 𝑤 the contents of its pushdown store be
sketch how such a parser 𝑃 works for an LR(0) grammar 𝜏0 𝛼1 𝜏1 𝛼2 · · · 𝜏𝑛−1 𝛼𝑛 𝜏𝑛 , for an integer 𝑛 ≥ 0,
𝐺 = (𝑁, Σ, 𝑆, 𝑅). The parser is actually a pushdown 𝜏0 , 𝜏1 , . . . , 𝜏𝑛 ∈ 𝒯 , 𝛼1 , . . . , 𝛼𝑛 ∈ (𝑁 ∪ Σ),
automaton that stores alternately symbols from 𝑁 ∪ Σ 𝑤 = 𝑧𝑟 𝑧, where 𝑧𝑟 ∈ Σ* is the already pro-
and certain tables. For a given LR(0) grammar, the set 𝒯 cessed prefix of 𝑤 and 𝑧 ∈ Σ* is the unread part
of possible tables is finite and there exist two functions of 𝑤.
𝑓 : 𝒯 → {𝑠ℎ𝑖𝑓 𝑡, 𝑒𝑟𝑟𝑜𝑟} ∪ {𝑟𝑒𝑑𝑢𝑐𝑒 𝜋 | 𝜋 ∈ 𝑅} is – If 𝑓 (𝜏𝑛 ) ̸= 𝑒𝑟𝑟𝑜𝑟, then there exists a word
the parsing action function, and 𝑡 such that 𝑆 ⇒*𝑅 𝛼1 · · · 𝛼𝑛 𝑡 ⇒*𝑅 𝑧𝑟 𝑡.
𝑔 : 𝒯 × (𝑁 ∪ Σ) → 𝒯 ∪ {𝑒𝑟𝑟𝑜𝑟} is the goto – If 𝑓 (𝜏𝑛 ) = 𝑒𝑟𝑟𝑜𝑟, then there is no word
function. 𝑡 such that 𝑆 ⇒*𝑅 𝛼1 · · · 𝛼𝑛 𝑧𝑡 ⇒*𝑅 𝑧𝑟 𝑡.
We will omit the details of how the set of tables 𝒯 That is, for all words 𝑡 ∈ Σ* , 𝑧𝑟 𝑡 ̸∈ 𝐿(𝐺).
and the functions 𝑓 and 𝑔 are constructed. But we will – There exist words 𝑧1 , 𝑧2 , . . . , 𝑧𝑛 ∈ Σ*
describe how the LR(0) parser for the LR(0) grammar 𝐺 such that 𝑧𝑟 = 𝑧1 · · · 𝑧𝑛 and 𝛼𝑖 ⇒*𝑅 𝑧𝑖 ,
works on an input word 𝑤. At first, an initial table 𝜏0 is for 𝑖 = 1, . . . , 𝑛. There exist derivation
sub-trees 𝑇1 , . . . , 𝑇𝑛 according to 𝐺 such 𝑇1 @ 𝑇𝑤
that the root of 𝑇𝑖 is labeled 𝛼𝑖 and the @
𝑇2
labels of the leaves of 𝑇𝑖 concatenated is @
the word 𝑧𝑖 , for 𝑖 = 1, . . . , 𝑛. @
𝐴 @
@ @
𝐴
3. LR(¢,$)-grammars @
@ @
@
@ 𝑢@ @
@
We introduce LR(¢,$)-grammars to obtain grammars that 𝑥 𝑢1 𝑣 2 𝑦
can control RP-automata in such a way that this type of
Figure 1: The structure of a derivation tree.
automata will characterize DCFL and regular languages
by pumping reductions.
Definition 6. Let ¢, $ ∈ / (𝑁 ∪ Σ) and 𝐺 = (𝑁, Σ ∪
{¢, $}, 𝑆, 𝑅) be an LR(0) grammar generating a lan-
3.1. Pumping notions by
guage of the form {¢} · 𝐿 · {$}, where 𝐿 ⊆ Σ* , and LR(¢,$)-Grammars
𝑆 does not occur in the right-hand side of any rule from 𝑅. This section studies the pumping properties of context-
We say that 𝐺 is an LR(¢,$)-grammar. We denote the set free grammars. We start with several definitions and
of LR(¢,$)-grammars by LRG(¢, $). W.l.o.g., we suppose notations.
that an LR(¢,$)-grammar does not contain rewriting rules Pumping reduction. Let 𝐺 = (𝑁, Σ, 𝑆, 𝑅) be a
of the form 𝐴 → 𝜆 for any nonterminal 𝐴 ∈ 𝑁 . context-free grammar, 𝑥, 𝑢1 , 𝑣, 𝑢2 , 𝑦 be words over Σ,
We say that 𝐿 is the internal language of 𝐺 and denote |𝑢1 | + |𝑢2 | > 0 and 𝐴 ∈ 𝑁 be a nonterminal. If
it as 𝐿𝐼𝑛 (𝐺).
𝑆 ⇒* 𝑥𝐴𝑦 ⇒* 𝑥𝑢1 𝐴𝑢2 𝑦 ⇒* 𝑥𝑢1 𝑣𝑢2 𝑦 (1)
Classes of languages. In what follows, ℒ(𝐴), where 𝐴
is some (sub)class of grammars or automata, denotes the we say that 𝑥𝑢1 𝑣𝑢2 𝑦 ⇐𝑃 (𝐺) 𝑥𝑣𝑦 is a pumping reduction
class of languages generated/accepted by grammars/au- according to grammar 𝐺. Here ⇒ denotes the rewrit-
tomata from 𝐴. E.g., the class of languages generated ing relation according to a rule of 𝐺 that need not be a
by linear LR(¢,$)-grammars is denoted by ℒ(𝑙𝑖𝑛-LR(¢,$)). right derivation. Then ⇒* is the reflexive and transitive
Similarly, for some (sub)class of LR(¢,$)-grammars 𝐴 we closure of ⇒.
take for internal languages ℒ𝐼𝑛 (𝐴) = {𝐿 | {¢}·𝐿·{$} ∈ If a word 𝑤 can be generated by 𝐺, then there exists a
ℒ(𝐴)}. sequence of words 𝑤1 , . . . , 𝑤𝑛 from Σ* , for some integer
Based on the closure properties of DCFL shown, e.g., in 𝑛 ≥ 1, such that 𝑤 = 𝑤1 , there are pumping reductions
[5], internal languages of LR(¢,$)-grammars can be used 𝑤𝑖 ⇐𝑃 (𝐺) 𝑤𝑖+1 , for all 𝑖 = 1, . . . , 𝑛 − 1, and there is no
to represent all deterministic context-free languages. pumping reduction 𝑤𝑛 ⇐𝑃 (𝐺) 𝑤𝑛+1 , for any 𝑤𝑛+1 ∈
Σ* .
Proposition 7. ℒ𝐼𝑛 (LRG(¢, $)) = 𝐷𝐶𝐹 𝐿.
Let 𝑇𝑤 be a derivation tree corresponding to deriva-
Proof. Let 𝐿 ⊂ Σ* , and 𝐿 be a DCFL. Let ¢ and $ be tion (1), where 𝑤 = 𝑥𝑢1 𝑣𝑢2 𝑦. See Fig. 1. The proper
not from Σ. We know from [5] that 𝐿 · {$} is a strict sub-trees 𝑇1 and 𝑇2 of 𝑇𝑤 are sub-trees whose roots are
deterministic language, i.e., it is accepted by a determin- labelled with the same nonterminal 𝐴, thus by replacing
istic pushdown automaton by empty store. Therefore, 𝑇1 with 𝑇2 properly inside of 𝑇𝑤 , we again get a deriva-
{¢} · 𝐿 · {$} is also a strict deterministic language. This tion tree, namely the derivation tree 𝑇𝑤(0) for the word
implies that there is an LR(¢,$)-grammar 𝐺 such that 𝑤(0) = 𝑥𝑣𝑦 ∈ 𝐿(𝐺).
𝐿(𝐺) = {¢} · 𝐿 · {$}. Analogously, by replacing 𝑇2 with a copy of 𝑇1 , we
On the other hand, if 𝐿 is the inner language of an get the derivation tree 𝑇𝑤(2) for a longer word 𝑤(2) =
LR(¢, $)-grammar, the language {¢} · 𝐿 · {$} is LR(0), 𝑥𝑢1 𝑣𝑢2 𝑦. If we replace 𝑇2 with 𝑇1 𝑖 times, we obtain
2 2
and it can be accepted by a deterministic pushdown au- the derivation tree 𝑇𝑤(𝑖+1) for the word 𝑤(𝑖 + 1) =
𝑖+1 𝑖+1
tomaton. Using closure properties of DCFL [5], we can 𝑥𝑢 1 𝑣𝑢 2 𝑦.
prove that 𝐿 is also in DCFL. That finishes the proof. Pumping tree, prefix, reduction, and their patterns.
Let 𝑥, 𝑢1 , 𝑣, 𝑢2 , 𝐴, 𝑦, 𝑇1 be as on Fig. 1.
Note. It is not hard to see that the languages from We say that 𝑝𝑝 = 𝑥𝑢1 𝑣𝑢2 is a pumping prefix by 𝐺
ℒ(𝐿𝑅𝐺(¢, $)) are prefix-free and suffix-free languages with the pumping pattern (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ). We also say
at the same time. that 𝑝𝑝 is an (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 )-pumping prefix. If |𝑢1 | > 0
and |𝑢2 | > 0, we say that 𝑝𝑝 is a two-sided pumping
prefix. Otherwise, we say that 𝑝𝑝 is a one-sided pumping
prefix by 𝐺.
We say that 𝑇1 is the pumping tree of 𝑝𝑝 . Let us recall maximal length of the right-hand side of the rules from
that, for any 𝑡 ∈ Σ* , it holds that 𝑥𝑢1 𝑣𝑢2 𝑡 ∈ 𝐿(𝐺) iff 𝑅. If 𝑇 is a non-pumping accepting tree according to 𝐺
𝑥𝑣𝑡 ∈ 𝐿(𝐺). then it cannot have more than 𝑘𝑡 terminal leaves. If 𝑇
Recall that we suppose that |𝑢1 𝑢2 | > 0. has more than 𝑘𝑡 leaves, then there exists a path from
a leaf to the root of 𝑇 containing at least 𝑡 + 1 nodes
Definition 8. Let 𝑝𝑝 be a (𝑥, 𝑢1 , 𝑣, 𝑢2 )-pumping prefix labelled by nonterminals, and 𝑇 is not a non-pumping
by 𝐺, and 𝑥, 𝑢1 , 𝑣, 𝑢2 , 𝐴, 𝑦, 𝑇1 be as on Fig. 1. We say tree. Let 𝐾 = 𝑘𝑡 . We say that 𝐾 is the grammar
𝐺 𝐺
that 𝑝𝑝 is an e-leftmost (elementary leftmost) pumping number of 𝐺.
prefix by 𝐺, and that (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ) is an e-leftmost Note that any word from 𝐿(𝐺) of length greater than
pumping pattern if there is no proper prefix of 𝑝𝑝 such that 𝐾 must contain a core pumping pattern by 𝐺. On the
𝐺
it has a pumping pattern different from (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ). other hand, the length of any non-pumping accepting
We say in this case that 𝑇1 is the e-leftmost pumping tree. word by 𝐺 is at most 𝐾 .
𝐺
Let 𝑧 be a word from Σ* . We write 𝑥𝑢1 𝑣𝑢2 𝑧 ⇐𝑃 (𝐺,𝑒) We can see the following obvious proposition that
𝑥𝑣𝑧, and say that 𝑥𝑢1 𝑣𝑢2 𝑧 ⇐𝑃 (𝐺,𝑒) 𝑥𝑣𝑧 is an e-leftmost summarizes the leftmost pumping properties of LR(¢, $)-
pumping reduction by 𝐺, and that (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ) is grammars, which we will use in the following text. It is
also the pumping pattern of the e-leftmost pumping re- a direct consequence of the previous definitions and the
duction 𝑥𝑢1 𝑣𝑢2 𝑧 ⇐𝑃 (𝐺,𝑒) 𝑥𝑣𝑧. We also say that properties of LR(0)-grammars and their LR(0) analyzers.
𝑥𝑢1 𝑣𝑢2 𝑧 ⇐𝑃 (𝐺,𝑒) 𝑥𝑣𝑧 is an e-leftmost (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 )-
pumping reduction by 𝐺, and that 𝑥𝑢1 𝑣𝑢2 ⇐𝑃 (𝐺,𝑒) 𝑥𝑣 Proposition 9. Let 𝐺 = (𝑁, Σ ∪ {¢, $}, 𝑅, 𝑆) be an
is the smallest e-leftmost (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 )-pumping reduc- LR(¢,$)-grammar generating (analyzing) the language
tion by 𝐺. {¢} · 𝐿 · {$}. Let 𝑝𝑝 be an e-leftmost pumping prefix
by 𝐺 with the pumping pattern (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ), and
Note that, in the above definition, the word 𝑥𝑢1 𝑣𝑢2 𝑧 𝑥𝑢 𝑣𝑢 ⇐
1 2 𝑃 (𝐺,𝑒) 𝑥𝑣 be the corresponding smallest e-
need not be generated by 𝐺, but 𝑥𝑢1 𝑣𝑢2 𝑧 ⇐𝑃 (𝐺,𝑒) 𝑥𝑣𝑧 leftmost pumping reduction by 𝐺. Then
is still an e-leftmost pumping reduction by 𝐺. This is
important, as we will use such reduction also when ana- (a) Any 𝑤 ∈ {¢} · 𝐿 · {$} determines its derivation
lyzing words not generated by 𝐺. tree 𝑇𝑤 by 𝐺 unambiguously.
The notion of e-leftmost pumping reduction gives us (b) An e-leftmost pumping prefix by 𝐺 determines its
a basis for a special type of analysis by reduction for pumping tree unambiguously.
𝐿(𝐺), and mainly for analysis by reduction for 𝐿𝐼𝑛 (𝐺). (c) 𝑥𝑢𝑚+11 𝑣𝑢2 𝑛+1 𝑧 ⇐𝑃 (𝐺,𝑒) 𝑥𝑢𝑚 1 𝑣𝑢2 𝑧 is an e-
𝑛
The next notions are the most important notions of this leftmost pumping reduction by 𝐺 for any 𝑚, 𝑛 ≥
paper. 0, and 𝑧 ∈ Σ* .
Core pumping pattern. We say that a pumping pattern (d) ¢𝑥𝑣𝑧$ ∈ 𝐿(𝐺) iff ¢𝑥𝑢𝑚 1 𝑣𝑢2 𝑧$ ∈ 𝐿(𝐺) for any
𝑚
(𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ) by 𝐺 is a core pumping pattern if there 𝑚 ≥ 0, and any 𝑧 ∈ Σ . *
is 𝑦 such that 𝑥𝑣𝑦 cannot be reduced by any pumping (e) Let 𝑃𝑟 = 𝑥𝑢1 𝑣𝑢2 𝑧 ⇐𝑃 (𝐺,𝑒) 𝑥𝑣𝑧 be an e-
reduction by 𝐺. We say that the tuple (𝑢1 , 𝐴, 𝑣, 𝑢2 ) is a leftmost pumping reduction by 𝐺. Then 𝑃𝑟 is deter-
pumping core by 𝐺. mined unambiguously by the e-leftmost pumping
One-sided and two-sided (core) pumping pattern. prefix 𝑥𝑢1 𝑣𝑢2 .
Let (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ) be a (core) pumping pattern by
(f) ¢𝑥𝑢𝑛 1 𝑣𝑢2 𝑧$ ∈ 𝐿(𝐺) iff ¢𝑥𝑢1
𝑚 𝑛+𝑘
𝑣𝑢𝑚+𝑘 𝑧$ ∈
𝐺. We say that (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ) is a one-sided (core) 2
𝐿(𝐺) for all 𝑚, 𝑛, 𝑘 ≥ 0.
pumping pattern if 𝑢1 = 𝜆, or 𝑢2 = 𝜆. We say that
(𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ) is a two-sided (core) pumping pattern if The previous proposition is essential for our further
𝑢1 ̸= 𝜆, and 𝑢2 ̸= 𝜆. considerations. It shows that, for a non-empty 𝑢1 , the
Non-pumping accepting trees/words/derivations. distance of the place of pumping from the left end is not
Let 𝑧 ∈ Σ* and limited, and the position of pumping is determined by
the pumping prefix of the pumping reduction.
𝑆 ⇒𝑅 𝛼0 ⇒𝑅 𝛼1 · · · 𝛼𝑛 ⇒𝑅 𝑧 (2) Observation. It is not hard to see that for any e-leftmost
pumping pattern 𝑃𝑙 = (𝑥, 𝑢1 , 𝐴, 𝑣, 𝑢2 ) there exists a
be a right derivation by 𝐺. Let 𝑇 be the derivation tree
prefix 𝑥1 of 𝑥 such that 𝑃𝑒 = (𝑥1 , 𝑢1 , 𝐴, 𝑣, 𝑢2 ) is a core
corresponding to derivation (2). Let no repetition of a
pumping pattern. We say that 𝑃𝑒 corresponds to 𝑃𝑙 .
nonterminal occurs on any path from the root of 𝑇 to a
leaf of 𝑇 . We say that 𝑇 is a non-pumping accepting tree, Example 1. Consider the non-regular deterministic
derivation (2) is a non-pumping accepting derivation, and context-free language 𝐿 = {¢𝑎𝑛 𝑏𝑛 $ | 𝑛 ≥ 1} with the
𝑧 is a non-pumping accepting word by 𝐺. internal language {𝑎𝑛 𝑏𝑛 | 𝑛 ≥ 1} that is generated by
Notation. Let 𝐺 = (𝑁, Σ, 𝑆, 𝑅) be an LR(¢,$)-grammar, the LR(¢,$) grammar 𝐺 = ({𝑆, 𝑆1 , 𝑎, 𝑏}, {𝑎, 𝑏}, 𝑅, 𝑆)),
𝑡 be the number of nonterminals of 𝐺, and 𝑘 be the
State Item set Reg. expression parsing action function 𝑓
0 {𝑆 → ·¢𝑆1 $} 𝜆 shift
1 {𝑆 → ¢ · 𝑆1 $, 𝑆1 → ·𝑎𝑆1 𝑏, 𝑆1 → ·𝑎𝑏} ¢ shift
2 {𝑆1 → 𝑎 · 𝑆1 𝑏, 𝑆1 → 𝑎 · 𝑏, 𝑆1 → ·𝑎𝑆1 𝑏, 𝑆1 → ·𝑎𝑏} ¢𝑎+ shift
3 {𝑆 → ¢𝑆1 · $} ¢𝑎+ 𝑆1 shift
4 {𝑆 → ¢𝑆1 $·} ¢𝑆1 $ reduce 𝑆 → ¢𝑆1 $
5 {𝑆1 → 𝑎𝑏·} ¢𝑎+ 𝑏 reduce 𝑆1 → 𝑎𝑏
6 {𝑆1 → 𝑎𝑆1 · 𝑏} ¢𝑎+ 𝑆1 shift
7 {𝑆1 → 𝑎𝑆1 𝑏·} ¢𝑎+ 𝑆1 𝑏 reduce 𝑆1 → 𝑎𝑆1 𝑏
Table 1
𝐿𝑅(0) automaton states and regular expressions representing words reaching the states from the initial state 0.
𝑇1 @ 𝑇𝑤 $
3 4
@ 𝑆1
𝑇2
¢
@
@ start 0 1 5
𝑆1 @ 𝑎 𝑏
𝑆1@
@
𝑎 2 6 7
@ @ 𝑆1 𝑏
@ @ @
@ @ 𝑦
@
𝑥 𝑎 𝑎𝑏 𝑏
Figure 3: 𝐿𝑅(0) automaton.
Figure 2: The structure of a derivation tree for 𝑤 = 𝑥𝑎𝑎𝑏𝑏𝑦 .
by 𝐺 is (𝑎, 𝑎, 𝑆1 , 𝑎𝑏, 𝑏) and ¢𝑎𝑎𝑎𝑏𝑏 ⇐𝑃 (𝐺) ¢𝑎𝑎𝑏 is an
with the following set of production rules 𝑅: e-leftmost (𝑎, 𝑎, 𝑆1 , 𝑎𝑏, 𝑏)-pumping reduction by 𝐺. Real-
ize that a pumping reduction by 𝐺 can be applied to any
𝑆 → ¢𝑆1 $
word ¢𝑎𝑘 𝑏𝑚 , where 𝑘, 𝑚 > 1, including the cases when
𝑆1 → 𝑎𝑆1 𝑏 | 𝑎𝑏
𝑘 ̸= 𝑚.
The grammar is reduced. Consider the sentence 𝛾 = Moreover, (𝜆, 𝑎, 𝑆1 , 𝑎𝑏, 𝑏) is a core pumping pattern by
¢𝑎𝑎𝑎𝑏𝑏𝑏$. 𝐺.
Table 1 lists the set of tables 𝒯 of the 𝐿𝑅(0) automa-
• The handle of 𝛾 (cf. Definition 4) is the pair (𝑆1 → ton for the grammar 𝐺 together with the corresponding
𝑎𝑏, 5), as parsing action function 𝑓 . The column with regular expres-
𝑆 ⇒*𝑅 ¢𝑎𝑎𝑆1 𝑏𝑏$ ⇒𝑅 ¢𝑎𝑎𝑎𝑏𝑏𝑏$ sions summarizes by which strings are the particular states
reachable from the initial state.
and the division of 𝛾 into 𝛼, 𝛽, 𝑤 is unique: Table 2 lists the corresponding goto function 𝑔 of the
LR(0) analyzer.
𝛾 = ¢𝑎𝑎 ⏟𝑎𝑏⏞ 𝑏𝑏$ . The goto function of the LR(0) automaton can be repre-
⏟ ⏞
sented as a finite automaton 𝐴 with tables as states (see
⏟ ⏞
𝛼 𝛽 𝑤
Fig. 3). Note that state 4 is accepting and states 5, 7 are
• We can see that 𝐺 is a linear LR(¢, $)-grammar, as
reducing.
(a) 𝑆 ⇒*𝑅 𝛼𝐴𝑤 ⇒𝑅 𝛼𝛽𝑤 = 𝜂𝑤 Let us interpret all reducing states of the LR(0) automaton
(b) 𝑆 ⇒*𝑅 𝛼′ 𝐴′ 𝑥 ⇒𝑅 𝛼′ 𝛽 ′ 𝑥 = 𝜂𝑤′ 𝐴 as accepting states of the finite automaton 𝐴. What
obviously implies (𝐴 → 𝛽, |𝛼𝛽|) = (𝐴′ → is the regular language accepted by automaton 𝐴? The
𝛽 ′ , |𝛼′ 𝛽 ′ |), because 𝐴 = 𝑆1 , 𝛼 = 𝑎𝑛 , 𝑤 = 𝑎𝑛 , language contains all prefixes 𝛼𝛽 (𝛼, 𝛽 ∈ (𝑁 ∪ Σ)* ) of
𝛽 = 𝑎𝑆1 𝑏, for some 𝑛 ≥ 0. right sentential forms according to 𝐺 (obtained from the
initial nonterminal using right derivation rewriting steps)
The pumping notions can be illustrated in Fig. 2 with a such that 𝛽 is a right-hand side of a production rule of 𝐺
derivation tree for 𝑤 = 𝑥𝑎𝑎𝑏𝑏𝑦 ∈ 𝐿(𝐺), where 𝑥 = ¢𝑎𝑖 , and there is no proper prefix that can be reduced according
𝑦 = 𝑏𝑖 $, for any 𝑖 ≥ 0. to 𝐺. Formally:
For 𝑥 = ¢𝑎, 𝑝𝑝 = ¢𝑎𝑎𝑎𝑏𝑏 is an e-leftmost 𝐿(𝐴) = {𝛼𝛽 | 𝛼, 𝛽 ∈ (𝑁 ∪ Σ)* , ∃𝑤 ∈ Σ* , 𝐴 ∈ 𝑁 :
(𝑎, 𝑎, 𝑆1 , 𝑎𝑏, 𝑏)-pumping prefix by 𝐺, and 𝑇1 is an e- 𝑆 ⇒*𝑅 𝛼𝐴𝑤 ⇒𝑅 𝛼𝛽𝑤}.
leftmost pumping tree of 𝑝𝑝 . The pumping pattern of 𝑝𝑝
State 𝜏 𝑔(𝜏, ¢) 𝑔(𝜏, 𝑎) 𝑔(𝜏, 𝑏) 𝑔(𝜏, $) 𝑔(𝜏, 𝑆) 𝑔(𝜏, 𝑆1 )
0 1 error error error error
1 error 2 error error 3
2 error 2 5 error 6
3 error error error 4 error
4
5
6 error error 7 error error
7
Table 2
Goto function 𝑔 of the LR(0) analyzer for grammar 𝐺. Note that for reduction states 4, 5, and 7 the goto function is not defined.
Similarly, the goto function is not defined for the initial nonterminal 𝑆 .
The automaton 𝐴 enables to distinguish two types of 𝑤 ∈ Σ* . The accepting and rejecting analytic trees are
errors with respect to 𝐿𝑖𝑛 (𝐺). distinguished by the nonterminal under their root.
One-sided LR(¢,$)-grammar. Let 𝐺 be an LR(¢,$)-
1) A correct non-empty prefix of 𝐿(𝐺) which is turned grammar. We say 𝐺 is a one-sided grammar if all its
incorrect by appending the right sentinel. This cor- core pumping patterns are one-sided infixes.
responds to all strings 𝛼 ∈ (¢ · {𝑎, 𝑏, 𝑆}* ) such
that, after reading a prefix 𝛼 of a sentential form, Definition 10. An LR(¢,$) grammar 𝐺 = (𝑁, Σ, 𝑆, 𝑅)
the automaton reaches a state 𝑠 ∈ {0, 1, 2, 6} is called a complete LR(¢,$) grammar if
with undefined transition for $. All such strings 1. 𝐿(𝐺) = {¢} · Σ* · {$}.
are represented by the regular expression 𝑅1 = 2. 𝑆 → 𝑆𝐴 | 𝑆𝑅 , where 𝑆𝐴 , 𝑆𝑅 ∈ 𝑁 , are the only
¢𝑎 + ¢𝑎 𝑆1 .
* + rules in 𝑅 containing the initial nonterminal 𝑆. No
2) A correct non-empty prefix of 𝐿(𝐺) which is other rule of 𝐺 contains 𝑆𝐴 or 𝑆𝑅 in its righthand
turned incorrect by appending one more symbol side.
from {𝑎, 𝑏, 𝑆1 }. This corresponds to all senten- 3. The languages 𝐿(𝑆𝐴 ) and 𝐿(𝑆𝑅 ) generated by
tial forms with a prefix of the form ¢𝛽𝑐, where the grammars 𝐺𝐴 = (𝑁, Σ, 𝑆𝐴 , 𝑅) and 𝐺𝑅 =
𝛽 ∈ {𝑎, 𝑏, 𝑆1 }* and 𝑐 ∈ {𝑎, 𝑏, 𝑆1 }, such that, (𝑁, Σ, 𝑆𝑅 , 𝑅), respectively, are disjoint and com-
after reading ¢𝛽, the automaton reaches a state plementary with respect to {¢} · Σ* · {$}. That
𝑠 ∈ {0, 1, 2, 3, 6} with an error transitions for 𝑐. is, 𝐿(𝐺𝐴 ) ∩ 𝐿(𝐺𝑅 ) = ∅ and 𝐿(𝐺) = 𝐿(𝐺𝐴 ) ∪
These strings are represented by the regular expres- 𝐿(𝐺𝑅 ) = {¢} · Σ* · {$}.
sion 𝑅2 = ¢𝑏+ ¢𝑆1 (𝑎+𝑏+𝑆1 )+ ¢𝑎+ 𝑆1 (𝑎+𝑆1 ). We will denote the grammar as 𝐺 = (𝐺𝐴 , 𝐺𝑅 ). Fur-
ther, we will call 𝐺𝐴 and 𝐺𝑅 as accepting and rejecting
Now, the 𝐿𝑅(¢, $)-grammar generating the language grammar of the complete LR(¢,$)-grammar 𝐺, respectively.
¢ · 𝐿(𝐺𝑖𝑛 ) · $ can be obtained by transforming the regular
expression Now we will prove the main theorem.
𝑅1 $ + 𝑅2 (𝑎 + 𝑏)* $ Theorem 1. For any LR(¢,$)-grammar 𝐺𝐴 , there exists a
into an equivalent regular grammar followed by adding complete LR(¢,$)-grammar 𝐺𝐶 = (𝐺𝐴 , 𝐺𝑅 ).
productions of the grammar 𝐺𝑖𝑛 . This is the essential Proof. Let 𝐺𝐴 = (𝑁𝐴 , Σ ∪ {¢, $}, 𝑆𝐴 , 𝑅𝐴 ) be an
observation for constructing complete LR(¢,$)-grammar LR(¢,$)-grammar. We will show how to construct a com-
below. plete LR(¢,$)-grammar 𝐺𝐶 = (𝐺𝐴 , 𝐺𝑅 ) = (𝑁𝐴 ∪ 𝑁𝑅 ∪
{𝑆}, Σ ∪ {¢, $}, 𝑆, 𝑅𝐴 ∪ 𝑅𝑅 ∪ {𝑆 → 𝑆𝐴 , 𝑆 → 𝑆𝑅 })
3.2. Complete LR(¢,$)-grammars such that 𝑆 and 𝑆𝑅 are new nonterminals not contained
in 𝑁𝐴 , 𝑆𝑅 is from the new set of nonterminals 𝑁𝑅 . The
In this section, we introduce the complete LR(¢, $)- construction utilizes the fact that for each word 𝑤 from
grammar that will be used for constructing scf-mon-RP- the complement of 𝐿(𝐺𝐴 ), LR(0) analyzer of 𝐺𝐴 can de-
automaton performing (complete) pumping analysis by tect the shortest prefix 𝑦 of 𝑤 such that each word of the
reduction on any word over its input alphabet Σ. A com- form 𝑦𝑢 belongs to the complement of 𝐿(𝐺𝐴 ), where
plete LR(¢, $)-grammar is a normalized grammar that an- 𝑤, 𝑦, 𝑣 ∈ (𝑁𝐴 ∪ Σ)* .
alyzes both its internal language and its complement and Let 𝒯 be the set of tables of the LR(0) analyzer for 𝐺𝐴
which, in its analytic mode, returns exactly one deriva- and 𝜏0 ∈ 𝒯 be the initial state (table) of the correspond-
tion tree for each input word of the form ¢𝑤$, where ing LR(0) automaton. Let 𝑁𝑅 = 𝒯 ∪ {𝐸}, where 𝐸 is
a new nonterminal not contained in 𝑁𝐴 ∪ 𝑁𝑅 . The set · · · ⇐𝑃 (𝐺,𝑒) 𝑢𝑛 , and there is not any 𝑧 such that
of rules 𝑅𝑅 will contain rules 𝐸 → 𝑎𝐸|$, for all 𝑎 ∈ Σ, 𝑢𝑛 ⇐𝑃 (𝐺,𝑒) 𝑧. We say that AR(𝐺𝑅 , 𝑢) is a pumping
for generating arbitrary suffixes of words from Σ* · {$}. analysis by reduction of 𝑢 by 𝐺𝑅 and by 𝐺 as well.
Based on the goto function 𝑔 of the LR(0) analyzer for Let 𝑢 ∈ 𝐿𝐼𝑛 (𝐺𝐴 ). We take AR(𝐺, 𝑢) = AR(𝐺𝐴 , 𝑢).
𝐺𝐴 , we add the following set of rules into 𝑅𝑅 Let 𝑢 ∈ 𝐿𝐼𝑛 (𝐺𝑅 ). We take AR(𝐺, 𝑢) = AR(𝐺𝑅 , 𝑢).
Let AR(𝐺) = {AR(𝐺, 𝑢) | 𝑢 ∈ Σ* }. We say that
{𝜏 → 𝑎𝐸 | 𝜏 ∈ 𝒯 , 𝑎 ∈ Σ ∪ 𝑁, 𝑔(𝜏, 𝑎) = 𝑒𝑟𝑟𝑜𝑟} ∪
AR(𝐺) is pumping analysis by reduction by 𝐺.
{𝜏 → $ | 𝜏 ∈ 𝒯 , 𝑔(𝜏, $) = 𝑒𝑟𝑟𝑜𝑟}.
Let AR(A, 𝐺) = {AR(𝐺, 𝑢)|𝑢 ∈ 𝐿(𝐺𝐴 )}. We say
(3)
that AR(A, 𝐺) is accepting pumping analysis by reduction
Now it is easy to see that all words of the form ¢𝑤$,
by 𝐺.
where 𝑤 ∈ Σ* , that are rejected by the LR(0) analyzer
Let AR(R, 𝐺) = {AR(𝐺, 𝑢)|𝑢 ∈ 𝐿(𝐺𝑅 )}. We say
for 𝐺 can be generated from the nonterminal 𝜏0 . Hence,
that AR(R, 𝐺) is rejecting pumping analysis by reduction
we set 𝑆𝑅 = 𝜏0 . Note that we did not include rules with
by 𝐺.
the left sentinel ¢ into the set defined in (3), because the
complete grammar should generate only words of the
form ¢𝑤$, for 𝑤 ∈ Σ* . 4. Pumping RP-automata
Additionally, the grammar 𝐺𝑅 = (𝑁𝐴 ∪ 𝑁𝑅 ∪
{𝑆}, Σ ∪ {¢, $}, 𝑆𝑅 , 𝑅𝐴 ∪ 𝑅𝑅 ∪ {𝑆 → 𝑆𝐴 , 𝑆 → 𝑆𝑅 })
controlled by complete
is an LR(¢,$)-grammar, as the corresponding LR(0) an- LR(¢,$)-grammars.
alyzer for 𝐺𝑅 can be obtained by modifying the LR(0)
analyzer for 𝐺𝐴 . In this section, we show that for any complete LR(¢,$)-
grammar obtained by the construction from the proof of
Observe that the complete grammar constructed ac- Theorem 1, we can construct an RP-automaton with the
cording to the above construction has further interesting same pumping analysis by reduction as 𝐺.
properties:
Theorem 2. Let 𝐺𝐶 = (𝑁, Σ, 𝑆, 𝑅) be a complete
1. For each word of the form ¢𝑤$, where 𝑤 ∈ Σ* ,
LR(¢,$)-grammar with an accepting grammar 𝐺𝐴 =
there is exactly one derivation tree 𝑇 according
(𝑁, Σ ∪ {¢, $}, 𝑆𝐴 , 𝑅) and a rejecting grammar 𝐺𝑅 =
to 𝐺𝐶 . Under the root of 𝑇 , there is a node la-
(𝑁, Σ ∪ {¢, $}, 𝑆𝑅 , 𝑅).
belled either by 𝑆𝐴 or 𝑆𝑅 . If it is 𝑆𝐴 , the word
Then there exists a procedure that constructs
is generated by the accepting grammar 𝐺𝐴 . Oth-
an scf-det-mon-RP-automaton 𝑀 (𝐺𝐶 ) =
erwise, it is generated by the rejecting grammar
(𝑄, Σ, ¢, $, 𝑞0 , 𝑘, 𝛿, 𝑄A , 𝑄R ) such that AR(𝑀 (𝐺𝐶 )) =
𝐺𝑅 .
AR(𝐺𝐶 ), AR(A, 𝑀 (𝐺𝐶 )) = AR(A, 𝐺𝐶 ), and
2. Let 𝑇 be a derivation tree according to 𝐺𝐶 . If a
AR(R, 𝑀 (𝐺𝐶 )) = AR(R, 𝐺𝐶 ).
node 𝑑 from 𝑇 is labelled by a nonterminal from
𝑁𝐴 , then all its descendant nodes are labelled Proof. The construction is based on the same idea as the
only by symbols from 𝑁𝐴 . construction of the det-mon-R-automaton 𝑀 simulat-
3. Let 𝑇 be a derivation tree according to 𝐺𝐶 . If a ing a syntactic analysis of a deterministic context-free
node 𝑑 from 𝑇 is labeled by a nonterminal from language 𝐿 in [6]. There, an analysis by reduction of the
𝑁𝑅 , then all nodes on the path from 𝑑 to the root automaton 𝑀 simulated a syntactic analysis according
of 𝑇 (except the root itself) are labelled only by to 𝐺. Here, we stress that 𝑀 (𝐺𝐶 ) will perform pumping
symbols from 𝑁𝑅 . analysis by reduction simulating syntactic analysis by
4. The new rules added in the above construction the complete LR(¢,$) grammar 𝐺𝐶 for any word over its
enable only one-sided pumping patterns. Thus, input alphabet. More precisely, in the cycles of its com-
if 𝐺𝐴 is a one-sided LR(¢, $)-grammar, then 𝐺𝑅 putation, 𝑀 (𝐺𝐶 ) performs a limited syntactic analysis
and 𝐺𝐶 have only one-sided core pumping pat- by 𝐺𝐴 and later possibly by 𝐺𝑅 . By this construction,
terns. we directly obtain deterministic monotone restarting au-
Definition 11. Let 𝐺 = (𝑁, Σ ∪ {¢, $}, 𝑆, 𝑅) be a com- tomaton in the strong cyclic form.
plete LR(¢,$)-grammar, 𝐺𝐴 and 𝐺𝑅 be its accepting and The second difference here is that we use
rejecting grammars. Let 𝑢 ∈ 𝐿𝐼𝑛 (𝐺𝐴 ), AR(𝐺, 𝑢) = det-mon-RP-automata instead of det-mon-R-auto-
(𝑢, 𝑢1 , 𝑢2 , . . . , 𝑢𝑛 ), where 𝑢 ⇐𝑃 (𝐺,𝑒) 𝑢1 ⇐𝑃 (𝐺,𝑒) mata. Let us note that each det-mon-R-automaton 𝑀
𝑢2 ⇐𝑃 (𝐺,𝑒) · · · ⇐𝑃 (𝐺,𝑒) 𝑢𝑛 , and there is not any 𝑧 can′ be easily converted into a det-mon-RP-automaton
such that 𝑢𝑛 ⇐𝑃 (𝐺,𝑒) 𝑧. We say that AR(𝐺𝐴 , 𝑢) is a 𝑀 by splitting each restarting instruction of 𝑀 into
pumping analysis (by reduction) of 𝑢 by 𝐺𝐴 and 𝐺 as well. one preparing instruction and one restarting instruction
Let 𝑢 ∈ 𝐿 (𝐺 ), AR(𝐺 , 𝑢) = (𝑢, 𝑢 , . . . , 𝑢 ), of 𝑀 .
′
𝐼𝑛 𝑅 𝑅 1 𝑛
where 𝑢 ⇐𝑃 (𝐺,𝑒) 𝑢1 ⇐𝑃 (𝐺,𝑒) 𝑢2 ⇐𝑃 (𝐺,𝑒)
𝑇1 @ 𝑇𝑤,𝐺𝐶 It is not hard to see from the previous construction
@ that 𝑀 (𝐺𝐶 ) is an scf-det-mon-RP-automaton such
𝑇2 @ that AR(𝑀 (𝐺𝐶 )) = AR(𝐺𝐶 ), AR(A, 𝑀 (𝐺𝐶 )) =
@ AR(A, 𝐺𝐶 ), and AR(R, 𝑀 (𝐺𝐶 )) = AR(R, 𝐺𝐶 ).
𝐴 @ The fact that 𝑀 (𝐺𝐶 ) is deterministic and monotone
follows from the construction of det-mon-R-automaton
@ @
𝐴
in [3]. The strong cyclic form of 𝑀 (𝐺𝐶 ) follows from
@ @
@ @
the fact that all words from {¢}·Σ* ·{$} are generated by
@ 𝑢@ @
@
𝑥 𝑢1 𝑣 2 𝑦
𝐺𝐶 and all accepting computations of the LR(0) analyzer
Figure 4: The structure of a derivation tree. for 𝐺𝐶 end with reducing the input into the initial non-
terminal 𝑆, hence 𝑀 (𝐺𝐶 ) accepts in tail computations
with a tape contents of the length at most 𝐾𝐺𝐶 < 𝑘.
To see that the resulting det-mon-RP-automaton
𝑀 (𝐺𝐶 ) performs pumping analysis by reduction by 𝐺𝐶 , Definition 12. Let 𝐺𝐶 = (𝐺𝐴 , 𝐺𝑅 ) be a complete
we sketch the construction of 𝑀 (𝐺𝐶 ). LR(¢, $)-grammar with the corresponding accepting gram-
By simulating a pumping analysis by reduction by mar 𝐺𝐴 and rejecting grammar 𝐺𝑅 . Let 𝑀 (𝐺𝐶 ) be the
𝐺𝐶 on a word 𝑤 ∈ {¢} · Σ* · {$}, we can construct the scf-det-mon-RP-automaton constructed by the construc-
derivation tree 𝑇𝑤,𝐺𝐶 according to grammar 𝐺𝐶 (the tion described in the proof of Theorem 2.
inner vertices of which are labeled with nonterminals We say that 𝑀 (𝐺𝐶 ) is an RP-automaton with pump-
and leaves correspond to terminal symbols). ing analysis by reduction according to 𝐺𝐶 , 𝑀 (𝐺𝐶 ) is
Thus, for any word 𝑤 ∈ {¢} · Σ* · {$} there is exactly an RP(LRG(¢,$))-automaton, and by ℒ(𝑅𝑃 (𝐿𝑅𝐺(¢, $)))
one derivation tree 𝑇𝑤,𝐺𝐶 by 𝐺𝐶 . Similarly, as in the we denote the class of all languages accepted by
case of the standard pumping lemma for context-free RP(𝐿𝑅𝐺(¢, $))-automata. Additionally, we say that
languages, we can take 𝑝 = 𝐾𝐺𝐶 such that, for any 𝐿(𝐺𝑅 ) is the rejecting language of 𝑀 (𝐺𝐶 ), and we denote
word 𝑤 of length greater than 𝑝, there are (complete) it as 𝐿𝑅 (𝑀 (𝐺𝐶 )).
subtrees 𝑇1 and 𝑇2 of 𝑇𝑤,𝐺𝐶 such that 𝑇2 is a subtree of
𝑇1 and the roots of both subtrees have the same label (cf. Corollary 1. For any LR(¢,$)-grammar 𝐺 there exists
Fig. 4); in addition, 𝑇2 has fewer leaves than 𝑇1 , 𝑇1 has a complete LR(¢,$)-grammar 𝐺𝐶 = (𝐺, 𝐺𝑅 ) and a de-
at most 𝑝 leaves, and |𝑢1 𝑢2 | > 0. terministic monotone RP(𝐿𝑅𝐺(¢, $))-automaton with a
Obviously, replacing 𝑇1 with 𝑇2 , we get the derivation pumping analysis by reduction according to 𝐺𝐶 such that
tree 𝑇𝑤(0) for a shorter word 𝑤(0) (if 𝑤 = 𝑥𝑢1 𝑣𝑢2 𝑦 𝐿𝐼𝑛 (𝐺) = 𝐿(𝑀 (𝐺𝐶 )), 𝐿𝐼𝑛 (𝐺𝑅 ) = 𝐿𝑅 (𝑀 (𝐺𝐶 )).
then 𝑤(0) = 𝑥𝑣𝑦). Lemma 1. ℒ(det-mon-RP) ⊆ DCFL.
The key to the construction of 𝑀 (𝐺𝐶 ) is the possibil-
ity to identify the leftmost sub-word 𝑢1 𝑣𝑢2 correspond- Proof. As the models of det-mon-R- and det-mon-RP-
ing to sub-trees 𝑇1 and 𝑇2 by 𝐺𝐶 , as shown in Fig. 4, automata differ only slightly, we can use here a
when reading from left to right with the help of a constant slightly modified proof of Lemma 8 in [6] stating that
size memory only. In its constant size memory, 𝑀 (𝐺𝐶 ) ℒ(det-mon-R) ⊆ DCFL. For given det-mon-RP-
stores all maximal sub-trees of the derivation tree(s) with automaton 𝑀 , a method from [6] can be used to construct
all their leaves in the buffer. This is done by simulating a deterministic push-down automaton 𝑃 that accepts the
the LR(0) analyzer for 𝐺𝐶 . When it identifies the leftmost same language as 𝑀 .
core pumping sub-tree like 𝑇1 above, 𝑀 (𝐺𝐶 ) deletes 𝑢1
and 𝑢2 by executing a single RESTART operation. As Theorem 3. ℒ(𝑅𝑃 (𝐿𝑅𝐺(¢, $)) = 𝐷𝐶𝐹 𝐿 =
the length of 𝑢1 𝑣𝑢2 is at most 𝑝, a read/write window of ℒ(det-mon-RP) = ℒ(scf-det-mon-RP)
length 𝑘 = 2𝑝 is sufficient for that.
If no such pumping sub-tree is built over the contents Proof. The theorem is a consequence of the previous
of the read/write window, the automaton 𝑀 (𝐺𝐶 ) for- lemma and the previous corollary.
gets the leftmost of these sub-trees with all its 𝑛 ≥ 1
leaves, and reads 𝑛 new symbols to the right end of the 5. Conclusion and Future Work
buffer (performing MVR-instructions). Then 𝑀 (𝐺𝐶 )
continues constructing the maximal sub-trees with all In this paper, we have introduced complete LR(¢,$)-
leaves in the (updated) buffer (again by simulating the grammars and restarting pumping RP(LRG(¢,$))-
LR(0) analyzer for 𝐺𝐶 ). automata. We have answered some basic questions
Short words of length less than 𝑘 are accepted/rejected concerning this type of automata and grammars. By
in tail computations.
simulating classical LR(0)-analysis for complete LR(¢,$)- [7] M. Procházka, Redukční automaty a syntaktické
grammars, RP(LRG(¢,$))-automata can perform pumping chyby, Phd-thesis, Faculty of Mathematics and
analysis by reduction for complete LR(¢,$)-grammars. Physics, Charles University, Prague, 2011. In Czech.
The constructions and results in this paper should
enable to introduce and study regular and non-
regular characteristics of two-sided pumping patterns
of RP(LRG(¢,$))-automata and LRG(¢,$)-grammars and
use such characteristics to prepare tools for localization
of syntactic errors of general (and special) deterministic
context-free languages. This way, we can extend and
refine results from [7].
Acknowledgments
The research has been supported by the grant 1/0601/20
of the Slovak Scientific Grant Agency VEGA (Dana Par-
dubská) and the grant 19-21198S of the Czech Science
Foundation (Daniel Průša).
References
[1] F. Mráz, D. Pardubská, M. Plátek, J. Šíma, Pump-
ing deterministic monotone restarting automata and
DCFL, in: M. Holena, T. Horváth, A. Kelemenová,
F. Mráz, D. Pardubská, M. Plátek, P. Sosík (Eds.), Pro-
ceedings of the 20th Conference Information Tech-
nologies – Applications and Theory (ITAT 2020),
volume 2718 of CEUR Workshop Proceedings, CEUR-
WS.org, 2020, pp. 51–58. URL: http://ceur-ws.org/
Vol-2718/paper13.pdf.
[2] M. Plátek, F. Mráz, D. Pardubská, D. Průša, J. Šíma,
On separations of LR(0)-grammars by two types of
pumping patterns, in: B. Brejová, L. Ciencialová,
M. Holena, F. Mráz, D. Pardubská, M. Plátek, T. Vinar
(Eds.), Proceedings of the 21st Conference Infor-
mation Technologies – Applications and Theory
(ITAT 2021), volume 2962 of CEUR Workshop Pro-
ceedings, CEUR-WS.org, 2021, pp. 140–146. URL:
http://ceur-ws.org/Vol-2962/paper05.pdf.
[3] P. Jančar, F. Mráz, M. Plátek, J. Vogel, On mono-
tonic automata with a restart operation, J. Au-
tom. Lang. Comb. 4 (1999) 287–311. doi:10.25596/
jalc-1999-287.
[4] M. Plátek, F. Otto, F. Mráz, On h-lexicalized
restarting list automata, J. Autom. Lang. Comb.
25 (2020) 201–234. URL: https://doi.org/10.25596/
jalc-2020-201. doi:10.25596/jalc-2020-201.
[5] M. A. Harrison, Introduction to Formal Language
Theory, Addison-Wesley, USA, 1978.
[6] P. Jančar, F. Mráz, M. Plátek, J. Vogel, Restarting
automata, in: H. Reichel (Ed.), Fundamentals of
Computation Theory, FCT ’95, volume 965 of Lecture
Notes in Computer Science, Springer, 1995, pp. 283–
292. doi:10.1007/3-540-60249-6_60.