# Grammars for Free: Toward Grammar Inference for Ad Hoc Parsers

Michael Schröder  0000-0003-1496-0531 TU WienViennaAustria
<EMAIL_ADDRESS>and  Jürgen Cito  TU Wien and Meta Platforms,
Inc.ViennaAustria<EMAIL_ADDRESS>
(2022)

###### Abstract.

Ad hoc parsers are everywhere: they appear any time a string is split, looped
over, interpreted, transformed, or otherwise processed. Every ad hoc parser
gives rise to a language: the possibly infinite set of input strings that the
program accepts without going wrong. Any language can be described by a formal
grammar: a finite set of rules that can generate all strings of that language.
But programmers do not write grammars for ad hoc parsers—even though they
would be eminently useful. Grammars can serve as documentation, aid program
comprehension, generate test inputs, and allow reasoning about language-
theoretic security. We propose an automatic grammar inference system for ad
hoc parsers that would enable all of these use cases, in addition to opening
up new possibilities in mining software repositories and bi-directional parser
synthesis.

††journalyear: 2022††copyright: acmlicensed††conference: New Ideas and
Emerging Results ; May 21–29, 2022; Pittsburgh, PA, USA††booktitle: New Ideas
and Emerging Results (ICSE-NIER’22), May 21–29, 2022, Pittsburgh, PA,
USA††price: 15.00††doi: 10.1145/3510455.3512787††isbn: 978-1-4503-9224-2/22/05

##  1\. Introduction

_Parsing_ is one of the fundamental activities in software engineering.
Following Grune and Jacobs (2008), we take parsing to mean “the process of
structuring a linear representation in accordance with a given grammar,” an
activity so common that pretty much every program performs some kind of
parsing at one point or another. Academically, parsing has been studied since
the very early days of computer science (Irons, 1983) and _formal language
theory_ , which has its origin in linguistics (Chomsky, 1957), provides the
foundation for an impressive amount of both theoretical results (Hopcroft and
Ullman, 1979) and practical applications (Grune and Jacobs, 2008). As part of
every-day programming, _regular expressions_ (Thompson, 1968) are probably the
biggest and most widely known success story of applied formal language theory.
But apart from regexes, only a small minority of programs, mainly compilers
and some protocol implementations, make explicit reference to the formal-
theoretic underpinnings of parsing, documenting grammars of their input
languages and making use of formalized parsing techniques such as parser
generators (Johnson and Sethi, 1990; Parr and Quong, 1995) or parser
combinator frameworks (Leijen and Meijer, 2001). The vast majority of parsing
code in software today is _ad hoc_.

The Python expression in Footnote 2 is a typical example of an _ad hoc
parser_. It transforms a string s into a list of integers xs. First, the split
function breaks s into its comma-separated substrings, then the map function
applies the int constructor to all substrings, turning each into a proper
integer value. This parser does not use any particular parsing techniques or
frameworks, just ordinary functions manipulating strings and transforming
values. A programmer writing this expression would most likely not think about
the fact that they are writing a parser. Splitting a comma-separated list of
values, just like extracting a command-line argument, reading a timestamp, or
any other minor programming task involving strings, barely registers as
parsing. Commonly, this kind of parsing code is deeply entangled with
application logic—a phenomenon known as _shotgun parsing_ (Momot et al.,
2016).

xs = map(int, s.split(’,’))

$\displaystyle s\ $ $\displaystyle\to\ int\mid int\ \texttt{,}\ s$
$\displaystyle int\ $ $\displaystyle\to\ space^{*}\ sign^{?}\ digit\
(\texttt{\\_}^{?}\ digit)^{*}\ space^{*}$ $\displaystyle digit\ $
$\displaystyle\to\
\texttt{0}\mid\texttt{1}\mid\texttt{2}\mid\texttt{3}\mid\texttt{4}\mid\texttt{5}\mid\texttt{6}\mid\texttt{7}\mid\texttt{8}\mid\texttt{9}$
$\displaystyle sign\ $ $\displaystyle\to\ \texttt{+}\mid\texttt{-}$
$\displaystyle space\ $ $\displaystyle\to\
\texttt{\textvisiblespace}\mid\texttt{\textbackslash
t}\mid\texttt{\textbackslash n}\mid\texttt{\textbackslash
v}\mid\texttt{\textbackslash f}\mid\texttt{\textbackslash r}$

$space$+-$digit$_$space$,

Figure 1. An ad hoc parser and its grammar.222The notation used here denotes
terminals with typewriter font and uses the common operators $*$, $+$, and $?$
for zero-or-more, one-or-more, and optional occurrences, respectively. The
vertical bar $\mid$ separates alternative productions, without precedence.
Parentheses are used for grouping in the usual way.

Footnote 2 also includes a complete grammar for this parser (assuming the
semantics of Python 3.9). It is not a particularly complex grammar, but it is
perhaps still surprising. Even an experienced Python programmer might be
unaware, for example, that the int constructor, in addition to allowing an
optional leading + or - sign, also permits leading zeroes, strips surrounding
whitespace, and ignores single _ characters that are used for grouping digits.
Looking at the grammar, we can see that the strings "12,304" and
"+01_2,3_0_4␣" will both be accepted by the parser, while the empty input ""
will crash the program. That the parser’s language excludes the empty string
is obvious from the grammar, but might be difficult to work out from looking
at the code alone.333The split function, when applied to an empty string,
returns a singleton list also containing an empty string (rather than an empty
list, as one might assume). The int constructor, applied to this empty string
via map, will then throw a runtime exception.

A grammar certainly reveals a great deal about a rather deceptively simple
looking expression, yet no programmer would actually write it down. Grammars
share the same fate as most other forms of specification: they are hard to
write, can be hard to read, and seem hardly worth the trouble—especially for
ad hoc parsers. _If we are not building whole houses, why should we draw
blueprints?_ (Lamport, 2015)

But there is a form of specification, one wildly more successful than
grammars, that we can draw inspiration from: _types_. Formal grammars are
similar to types, in that a parser without a grammar is very much like a
function without a type signature. Types have one significant advantage over
grammars, however: most type systems offer a form of _type inference_ ,
allowing programmers to omit type annotations because they can be
automatically recovered from the surrounding context.444For a good
introduction to type inference and its history, see (MacQueen et al., 2020, §
4). If we could infer grammars like we can infer types, we could reap all the
rewards of having a complete specification of our program’s input language,
without burdening the programmer with the full weight of formal language
theory.

In this work, we sketch a possible path towards inferring grammars for ad hoc
parsers by combining methods found in refinement types and string constraint
solving. We describe future possibilities where grammar inference enables,
among other things, better program comprehension by explicitly documenting a
program’s input space, and bi-directional parser synthesis that helps
developers refine and secure their input validation.

##  2\. The Need for Grammars

Before we delineate how to statically infer grammars, we want to briefly
motivate why every (ad hoc) parser would greatly benefit from having a known
grammar.

#### Documentation

A formal grammar is the ideal documentation for a parser, because it provides
a high-level perspective that focuses on the _data_ as opposed to the code. It
allows the programmer to grasp the input language as is, without being
distracted by the mechanics of the implementation. There exist numerous
notations for grammars, each suitable for different languages and in different
contexts: regular expressions (Thompson, 1968), Chomsky normal form (Chomsky,
1959), Augmented Backus-Naur Form (ABNF) (Crocker and Overell, 2008), parsing
expression grammars (PEGs) (Ford, 2004), etc. Graphic representations, like
finite state machines (Hopcroft and Ullman, 1979) or railroad diagrams (Braz,
1990) (see Footnote 2), can be particularly helpful in understanding abstract
data and align with developers’ appreciation of sketches and diagrams (Baltes
and Diehl, 2014).

#### Program Comprehension

It is known that providing alternative representations for a programming task
can increase program comprehension (Gilmore and Green, 1984; Fitter and Green,
1979). The example in Footnote 2 demonstrates how a grammar can elucidate the
corresponding ad hoc parsing code, revealing otherwise hidden features and
potentially bugs or security issues. Because a grammar is also a _generating
device_ , it is possible to construct any sentence of its language in a finite
number of steps—manually or in an automated fashion. Generating concrete
examples of possible inputs further helps in understanding parsing code, and
can be invaluable during testing and debugging.

#### Fuzzing

We can test programs by bombarding them with (systematically generated) random
inputs and seeing if anything breaks. This is known as fuzz testing, or
fuzzing (Zeller et al., 2021; Manes et al., 2019). Generating good fuzz inputs
is not easy, because in order to penetrate into deep program states, one
generally needs valid or near-valid inputs, meaning inputs that pass at least
the various syntactic checks and transformations—i.e. ad hoc parsers—scattered
throughout a typical program. One promising approach is _grammar-based
fuzzing_ (Holler et al., 2012; Aschermann et al., 2019), where valid inputs
are specified with the help of language grammars.

#### Language-Theoretic Reasoning

As formal descriptions of input languages, grammars allow us to reason about
various language-theoretic properties, such as computability bounds. The
_language-theoretic security_ (LANGSEC) community555https://langsec.org
regards such reasoning as vital in assuring the correctness and safety of
input handling routines. For example, if an input language is recursively
enumerable, we can never guarantee that its parser behaves safely (i.e. halts)
on inputs that are not in the language, because the parser must be equivalent
to a Turing machine. Thus, input languages should be minimally powerful, and
their parsers should match them in computational power (Sassaman et al.,
2013). Ad hoc parsers open themselves up to attack, because it is not clear
what languages they implement, or if they implement them correctly, and
variations among implementations are easily overlooked (Schneeweisz, 2020).
Grammars can help assure us that our input languages have favorable properties
and that their parsers are implemented correctly.

#### Automatic Parser Generation

A _parser generator_ is a tool that synthesizes a parser from a given grammar.
Examples include Yacc (Johnson and Sethi, 1990), ANTLR (Parr and Quong, 1995),
and OMeta (Warth and Piumarta, 2007). These tools are common in certain areas,
such as compilers, and are usually invoked during program build time,
generating parsing code that is linked with the rest of the program. The great
advantage of starting with a grammar and letting the parser implementation be
generated automatically is a high assurance of correctness, as well as easier
maintainability.

##  3\. Toward Grammar Inference

We hope to realize automatic grammar inference based on the following
intuition: Any parser is essentially a _machine_ in the formal sense—it is a
recognizer for its input language.

###  3.1. Background: Languages & Machines

Formally, a _language_ $L$ is a possibly infinite set of sentences over a
finite alphabet $\Sigma$. We can define languages very abstractly, as in
$L=\\{a^{n}b^{n}\mid n>0\\}$, a language over the alphabet $\Sigma=\\{a,b\\}$
that consists of all sentences with at least one $a$ followed by the same
number of $b$s. Usually, however, we define languages via generative devices
called _grammars_ or recognizing devices called _machines_.

A grammar $G=(V,\Sigma,P,S)$ is a finite description of a language and
consists of a set of _variables_ (or _nonterminals_) $V$; a _terminal_
alphabet $\Sigma$; a set of _productions_ $P$, which are rules of the form
$\alpha\to\beta$ where $\alpha$ and $\beta$ are from $V$ and/or $\Sigma$; and
a _start symbol_ $S\in V$. By starting with $S$ and applying a finite number
of productions from $P$, we can generate sentences over $\Sigma$. The language
$L(G)$ is the set of all sentences that can be generated by $G$. By putting
various constraints on the _form_ of a grammar, such as whether the left-hand
side of a production can only include variables, or the right-hand side has to
include at least one terminal symbol, and so on, we can limit the grammar’s
expressiveness, constraining the _family_ of languages a grammar of this form
can produce. The famous Chomsky hierarchy (Chomsky, 1959) partitions
languages/grammars into four increasingly expressive levels: _regular_ ,
_context-free_ , _context-sensitive_ , and _recursively enumerable_. Numerous
additional language families and types of grammars have been discovered,
within and beyond the classic hierarchy: _attribute grammars_ (Knuth, 1968),
_boolean grammars_ (Okhotin, 2004, 2013), the _mildly context-sensitive_ and
_sub-regular_ languages (Jäger and Rogers, 2012), _parsing expression
grammars_ (PEGs) (Ford, 2004), to name just a few.

A machine $M$, unlike a grammar, does not produce sentences but consumes them.
Taking some sentence as input and moving through a finite number of internal
states, it arrives at some halting configuration if and only if the sentence
is part of the language $L(M)$. If the sentence is not part of the language,
the machine either runs forever or gets stuck in a non-accepting state. Just
like with grammars, the way that a machine is constructed determines its
expressiveness. There is a natural correspondence between languages, grammars,
and machines: regular languages correspond to _finite state machines_ , which
simply move from one internal state to another based on the next input
character; context-free languages correspond to finite state machines equipped
with a pushdown stack, also known as _pushdown automata_ ; context-sensitive
languages correspond to _linearly bounded automata_ , in essence Turing
machines with a finite tape; and finally the recursively enumerable languages
correspond to the well-known unbounded _Turing machines_. As with grammars,
there are numerous additional and alternative constructions between and beyond
these classic ones.

Figure 2. Sketch of our grammar inference system.

###  3.2. Intuition: Parsers are Embedded Machines

A parser, like the Python snippet in Footnote 2, which expects a string from
some language $L_{1}$ as input, can be seen as a machine $M_{1}$ recognizing
that language, so that $L_{1}=L(M_{1})$. This machine is however embedded
within the more powerful machine $M_{0}$, the general-purpose programming
language that the parser itself is written in. Any real world parser will do
more than just recognize a language: it will allocate and transform data
types, throw exceptions or handle parse errors, or perform side effects
unrelated to the parsing process itself. Nevertheless, the control flow at the
core of a parser will, in our experience, closely match that of the
(hypothetical) machine $M_{1}$. While it is entirely possible that a parser
written in a Turing-complete programming language exhibits exactly those
traits that make it equivalent to a Turing machine, even though it might be
parsing a “lesser” language, we think this to be very unlikely. In almost all
practical situations, ad hoc parsing code will not significantly exceed the
“power-level” of the language it is parsing. For example, unless it has been
especially constructed to be confounding, the loops present in a parser will
invariably be bounded by at most some linear factor of the length of its
input, which corresponds to the expressiveness of a context-sensitive
language. Thus, we think it is feasible to transform ad hoc parsers into
equivalent machines whose languages can be statically inferred.

###  3.3. Vision: Automatic Grammar Inference

Figure 2 shows a sketch of the end-to-end grammar inference system that we
envision. In the first step, ad hoc parsing code is transformed from a Turing-
complete source language (e.g. Python) into an intermediate representation
(IR) that is essentially a domain-specific language for parsing. This
transformation can be seen as a simplification: it removes syntactic sugar,
makes control flow explicit, and throws away all parts of the source code that
are not related to parsing. During this step, known string processing
functions are translated into one or more equivalent functions of the IR that
precisely model the semantics of the source. To illustrate, let us consider a
slightly extended version of the example from Footnote 2:

⬇

1def vector_length(s):

2 [x,y,z] = map(int, s.split(’,’))

3 return math.sqrt(x**2 + y**2 + z**3)

The simplification results in roughly the following IR:

⬇

1let parse = $\lambda$(s : String {$\star$}).

2 let $\nu_{1}$ = split${}_{\texttt{py}}$ "," s in

3 let xs = map int${}_{\texttt{py}}$ $\nu_{1}$ in

4 let $\nu_{2}$ = length xs in

5 let $\nu_{3}$ = equals 3 $\nu_{2}$ in

6 assert $\nu_{3}$

Note that this function does not actually return anything. The goal here is
not to run it and obtain a result, but to fill the hole ($\star$) in its input
type by inferring the appropriate string constraints. To this end, the
functions $\texttt{split}_{\texttt{py}}$ and $\texttt{int}_{\texttt{py}}$
precisely model their Python counterparts and refine their input and output
types by imposing the constraints resulting from their modeled string
processing behavior. Note also how a remnant of the pattern match [x,y,z] from
the source is present in form of an (indirect) constraint on the length of the
string (lines 4–6 in the IR).

Inferring the type of parse and solving its string constraints results in a
model of the original ad hoc parser’s input language. To make the resulting
grammar traceable to the originating code, the model also contains rich source
location information, which has to be threaded through both the simplification
and inference steps. In a final step, the language model can then be used to
generate the desired textual, visual, and interactive grammar representations.

##  4\. Related Work

#### Grammatical Inference

A related but different problem to our goal of finding a grammar given a
parser is to find a grammar given a set of sentences. This is known as
_grammatical inference_ or _grammar induction_. Early results in computational
linguistics quickly established fundamental limits of what could be achieved:
it was shown that not even regular languages can be identified given only
positive examples (Gold, 1967). Nevertheless, with applications ranging from
speech recognition to computational biology, grammatical inference is an
active and vibrant field (de la Higuera, 2005; de la Higuera, 2010).

#### Fuzzing

A big problem in grammar-based fuzzing (cf. § 2) is obtaining accurate
grammars or language models. Black-box approaches try to infer a language
model by poking the program with seed inputs and monitoring its runtime
behavior (Bastani et al., 2017; Godefroid et al., 2017). This has some
theoretical limits (Angluin, 1987; Angluin and Kharitonov, 1995) and the
amount of necessary poking (i.e. membership queries) grows exponentially with
the size of the grammar. White-box approaches make use of the program code and
can thus use more sophisticated analysis techniques, e.g. taint tracking to
monitor data flow between variables (Höschele and Zeller, 2016) or tracking
dynamic control flow and observing character accesses of input strings
(Gopinath et al., 2020). These approaches rely on dynamic execution, but can
produce fairly accurate and human-readable grammars, at least in test
settings. They can not, however, provide any guarantees of correctness, and
thus it is not possible to determine how accurate the resulting grammars
really are. In our vision, grammars are _statically_ inferred from source code
and are always _sound_. By not relying on dynamic execution of whole programs,
grammars can be extracted from individual functions or even partial programs,
and it is not necessary to generate seed inputs to bootstrap inference.

#### String Constraint Solving

String constraints are relations defined over string variables and arise out
of program statements that manipulate strings, e.g. concatenation or substring
replacement. Reasoning about strings requires solving combinatorial problems
involving such constraints, which is difficult to do both efficiently and
completely, and a large number of approaches have been developed (Amadini,
2021; Stanford et al., 2021). Our problem of grammar inference is in some ways
the inverse: instead of wanting to model all possible strings a function can
return or express, we want to model all possible strings a function can accept
(without throwing an error or getting stuck).

##  5\. New Possibilities

The end-to-end grammar inference system we envision (§ 3) will not only let us
enjoy all the benefits that formal grammars provide in general (§ 2), it also
enables some exciting new possibilities.

#### Interactive Documentation

A grammar that is automatically inferred will always be up-to-date—a
significant advantage over manually written documentation, which tends to
quickly drift from the object it documents (Lethbridge et al., 2003).
Furthermore, an inferred grammar could be closely linked directly to the
underlying source code, making productions traceable to their origins. One can
imagine an interactive environment where hovering over parts of a grammar
highlights the corresponding pieces of code—or even allows changing them by
manipulating the high-level representation.

#### Bi-directional Parser Synthesis

Combining grammar inference with parser generation enables a framework of bi-
directional parser synthesis. In the most basic case, starting from an
existing complete parser implementation, the synthesizer can be used to
generate different implementations according to certain criteria, e.g.
performance or code style, by transformation via the inferred grammar—a
specialized type of semantic program transformation (Cousot and Cousot, 2002).
If the initial parser is incomplete, a bi-directional parser synthesizer can
be used for _program sketching_ (Solar-Lezama, 2008; Lubin et al., 2020;
Polikarpova et al., 2016), wherein an initial implementation (a “sketch”) is
the basis of an initial grammar which can be manipulated by the user on a high
level—perhaps graphically—to then in turn synthesize a completed or refined
implementation. If the sketch-synth loop can be sufficiently shortened, it can
be the basis for a direct manipulation bi-directional programming system
(Mayer et al., 2018; Chugh et al., 2016), although based on transformations of
the (specification of) inputs to the program rather than its outputs.

#### Mining & Learning

An inferred grammar abstracts over the underlying concrete parser
implementation and can be viewed as an equivalence class, allowing us to group
together different parser implementations with similar semantics.666While
there are a number of theoretical bounds regarding the decidability of
properties about grammars, it is in fact possible to efficiently decide
equivalence for many types of grammars encountered in practice (Madhavan et
al., 2015). This opens up new possibilities in mining software repositories,
such as grammar-enhanced semantic code search (Mishne et al., 2012; García-
Contreras et al., 2016; Premtoon et al., 2020) or detecting code clones
(Juergens et al., 2009; Yu et al., 2019) of ad hoc parsers. By automatically
inferring grammars for each code change, it also becomes possible to learn how
(implicit) input specifications evolve over time, enabling a type of grammar-
aware semantic change tracking (Raghavan et al., 2004; Hanam et al., 2019).
Augmenting the code review process with current as well as historical grammar
information would allow developers to be alerted when a code change introduces
a perhaps unexpected change in input grammar.

##  6\. Future Plans

We want to build the grammar inference system described in this paper and
apply it in real-world situations. We plan to realize our vision in a series
of upcoming works:

  * •

We are currently conducting a mining study of ad hoc parsers in the wild,
collecting common coding patterns in order to determine the possible scope of
our system.

  * •

We are currently investigating the use of refinement types (Jhala and Vazou,
2020) in combination with string constraint solving to realize inference of a
language model from a simplified parsing IR. While we have seen initial
success with smaller examples, we need to expand to more kinds of parsers to
understand our scope and limitations.

  * •

To ensure the validity of our approach, both simplification and inference need
to be proven sound. We plan on supplying machine-checked proofs for both of
these steps.

  * •

To ensure the effectiveness of our approach, we plan on evaluating the system
on a corpus of curated ad hoc parser samples from the real world. We have
begun collection of a suitable dataset.

  * •

We plan on conducting a large-scale mining study of inferred grammars, to
demonstrate the usefulness of our system to applications of code mining and
learning.

  * •

We plan on conducting a number of user studies on grammar comprehension in
order to determine the benefits and drawbacks of different textual and visual
grammar representations.

We are excited about the prospects of automated grammar inference and invite
the community to collaborate with us to realize our vision of “grammars for
free”.

## References

  * (1)
  * Amadini (2021) Roberto Amadini. 2021\.  A Survey on String Constraint Solving.  arXiv:2002.02376 [cs.AI]
  * Angluin (1987) Dana Angluin. 1987\.  Queries and Concept Learning.  _Mach. Learn._ 2, 4 (1987), 319–342.
  * Angluin and Kharitonov (1995) Dana Angluin and Michael Kharitonov. 1995.  When Won’t Membership Queries Help?  _J. Comput. System Sci._ 50, 2 (1995), 336–355.
  * Aschermann et al. (2019) Cornelius Aschermann, Tommaso Frassetto, Thorsten Holz, Patrick Jauernig, Ahmad-Reza Sadeghi, and Daniel Teuchert. 2019.  NAUTILUS: Fishing for Deep Bugs with Grammars. In _26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, February 24-27, 2019_.
  * Baltes and Diehl (2014) Sebastian Baltes and Stephan Diehl. 2014.  Sketches and Diagrams in Practice. In _Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering_ (Hong Kong, China) _(FSE 2014)_. 530–541.
  * Bastani et al. (2017) Osbert Bastani, Rahul Sharma, Alex Aiken, and Percy Liang. 2017\.  Synthesizing Program Input Grammars.  _SIGPLAN Not._ 52, 6 (June 2017), 95–110.
  * Braz (1990) Lisa M Braz. 1990\.  Visual syntax diagrams for programming language statements.  _ACM SIGDOC Asterisk Journal of Computer Documentation_ 14, 4 (1990), 23–27.
  * Chomsky (1957) Noam Chomsky. 1957\.  _Syntactic Structures_.  Mouton & Co. 117 pages.
  * Chomsky (1959) Noam Chomsky. 1959\.  On Certain Formal Properties of Grammars.  _Information and Control_ 2, 2 (1959), 137–167.
  * Chugh et al. (2016) Ravi Chugh, Brian Hempel, Mitchell Spradlin, and Jacob Albers. 2016\.  Programmatic and Direct Manipulation, Together at Last. In _Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Santa Barbara, CA, USA) _(PLDI ’16)_. 341–354.
  * Cousot and Cousot (2002) Patrick Cousot and Radhia Cousot. 2002.  Systematic Design of Program Transformation Frameworks by Abstract Interpretation. In _Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ (Portland, Oregon) _(POPL ’02)_. 178–190.
  * Crocker and Overell (2008) D. Crocker and P. Overell. 2008.  _Augmented BNF for Syntax Specifications: ABNF_.  STD 68. RFC Editor.
  * de la Higuera (2005) Colin de la Higuera. 2005\.  A bibliographical study of grammatical inference.  _Pattern Recognition_ 38, 9 (2005), 1332–1348.  Grammatical Inference.
  * de la Higuera (2010) Colin de la Higuera. 2010\.  _Grammatical Inference: Learning Automata and Grammars_.  Cambridge University Press.
  * Fitter and Green (1979) M Fitter and TRG Green. 1979.  When do diagrams make good computer languages?  _International Journal of man-machine studies_ 11, 2 (1979), 235–261.
  * Ford (2004) Bryan Ford. 2004\.  Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. In _Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ (Venice, Italy) _(POPL ’04)_. 111–122.
  * García-Contreras et al. (2016) Isabel García-Contreras, José F. Morales, and Manuel V. Hermenegildo. 2016.  Semantic code browsing.  _Theory and Practice of Logic Programming_ 16, 5-6 (2016), 721–737.
  * Gilmore and Green (1984) David J. Gilmore and Thomas R. G. Green. 1984.  Comprehension and recall of miniature programs.  _International Journal of Man-Machine Studies_ 21, 1 (1984), 31–48.
  * Godefroid et al. (2017) Patrice Godefroid, Hila Peleg, and Rishabh Singh. 2017\.  Learn & Fuzz: Machine Learning for Input Fuzzing. In _Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering_ (Urbana-Champaign, IL, USA) _(ASE 2017)_. IEEE Press, 50–59.
  * Gold (1967) E Mark Gold. 1967\.  Language identification in the limit.  _Information and control_ 10, 5 (1967), 447–474.
  * Gopinath et al. (2020) Rahul Gopinath, Björn Mathis, and Andreas Zeller. 2020\.  Mining Input Grammars from Dynamic Control Flow. In _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ (Virtual Event, USA) _(ESEC/FSE 2020)_. 172–183.
  * Grune and Jacobs (2008) Dick Grune and Ceriel J. H. Jacobs. 2008.  _Parsing Techniques_ (2nd ed.).  Springer, New York, NY.
  * Hanam et al. (2019) Quinn Hanam, Ali Mesbah, and Reid Holmes. 2019.  Aiding Code Change Understanding with Semantic Change Impact Analysis. In _2019 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. 202–212.
  * Holler et al. (2012) Christian Holler, Kim Herzig, and Andreas Zeller. 2012\.  Fuzzing with Code Fragments. In _Proceedings of the 21st USENIX Conference on Security Symposium_ (Bellevue, WA) _(Security’12)_. USENIX Association, USA, 38\.
  * Hopcroft and Ullman (1979) John Hopcroft and Jeffrey Ullman. 1979.  _Introduction to Automata Theory, Languages, and Computation_.  Addison-Wesley.
  * Höschele and Zeller (2016) Matthias Höschele and Andreas Zeller. 2016.  Mining Input Grammars from Dynamic Taints. In _Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering_ (Singapore, Singapore) _(ASE 2016)_. 720–725.
  * Irons (1983) Edgar T. Irons. 1983\.  A Syntax Directed Compiler for ALGOL 60.  _Commun. ACM_ 26, 1 (Jan. 1983), 14–16.
  * Jäger and Rogers (2012) Gerhard Jäger and James Rogers. 2012.  Formal language theory: refining the Chomsky hierarchy.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ 367, 1598 (2012), 1956–1970.
  * Jhala and Vazou (2020) Ranjit Jhala and Niki Vazou. 2020.  Refinement Types: A Tutorial.  (2020).  arXiv:2010.07763 [cs.PL]
  * Johnson and Sethi (1990) Stephen C Johnson and Ravi Sethi. 1990.  Yacc: A Parser Generator.  _UNIX Vol. II: Research System_ (1990), 347–374.
  * Juergens et al. (2009) Elmar Juergens, Florian Deissenboeck, Benjamin Hummel, and Stefan Wagner. 2009.  Do code clones matter?. In _2009 IEEE 31st International Conference on Software Engineering_. 485–495.
  * Knuth (1968) Donald E Knuth. 1968\.  Semantics of context-free languages.  _Mathematical systems theory_ 2, 2 (1968), 127–145.
  * Lamport (2015) Leslie Lamport. 2015\.  Who builds a house without drawing blueprints?  _Commun. ACM_ 58, 4 (2015), 38–41.
  * Leijen and Meijer (2001) Daan Leijen and Erik Meijer. 2001.  Parsec: Direct style monadic parser combinators for the real world.  (2001).
  * Lethbridge et al. (2003) T.C. Lethbridge, J. Singer, and A. Forward. 2003\.  How software engineers use documentation: the state of the practice.  _IEEE Software_ 20, 6 (2003), 35–39.
  * Lubin et al. (2020) Justin Lubin, Nick Collins, Cyrus Omar, and Ravi Chugh. 2020\.  Program Sketching with Live Bidirectional Evaluation.  _Proc. ACM Program. Lang._ 4, ICFP, Article 109 (Aug. 2020), 29 pages.
  * MacQueen et al. (2020) David MacQueen, Robert Harper, and John Reppy. 2020\.  The History of Standard ML.  _Proc. ACM Program. Lang._ 4, HOPL, Article 86 (June 2020), 100 pages.
  * Madhavan et al. (2015) Ravichandhran Madhavan, Mikaël Mayer, Sumit Gulwani, and Viktor Kuncak. 2015.  Automating Grammar Comparison. In _Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications_ (Pittsburgh, PA, USA) _(OOPSLA 2015)_. 183–200.
  * Manes et al. (2019) Valentin J. M. Manes, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, and Maverick Woo. 2019\.  The Art, Science, and Engineering of Fuzzing: A Survey.  arXiv:1812.00140 [cs.CR]
  * Mayer et al. (2018) Mikaël Mayer, Viktor Kuncak, and Ravi Chugh. 2018\.  Bidirectional Evaluation with Direct Manipulation.  _Proc. ACM Program. Lang._ 2, OOPSLA, Article 127 (Oct. 2018), 28 pages.
  * Mishne et al. (2012) Alon Mishne, Sharon Shoham, and Eran Yahav. 2012\.  Typestate-Based Semantic Code Search over Partial Programs. In _Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications_ (Tucson, Arizona, USA) _(OOPSLA ’12)_. 997–1016.
  * Momot et al. (2016) Falcon Darkstar Momot, Sergey Bratus, Sven M Hallberg, and Meredith L Patterson. 2016.  The Seven Turrets of Babel: A Taxonomy of LangSec Errors and How to Expunge Them. In _2016 IEEE Cybersecurity Development (SecDev)_. IEEE, 45–52.
  * Okhotin (2004) Alexander Okhotin. 2004\.  Boolean grammars.  _Information and Computation_ 194, 1 (2004), 19–48.
  * Okhotin (2013) Alexander Okhotin. 2013\.  Conjunctive and Boolean grammars: the true general case of the context-free grammars.  _Computer Science Review_ 9 (2013), 27–59.
  * Parr and Quong (1995) Terence J. Parr and Russell W. Quong. 1995.  ANTLR: A predicated-LL (k) parser generator.  _Software: Practice and Experience_ 25, 7 (1995), 789–810.
  * Polikarpova et al. (2016) Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. 2016\.  Program Synthesis from Polymorphic Refinement Types. In _Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Santa Barbara, CA, USA) _(PLDI ’16)_. 522–538.
  * Premtoon et al. (2020) Varot Premtoon, James Koppel, and Armando Solar-Lezama. 2020\.  Semantic Code Search via Equational Reasoning. In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_ (London, UK) _(PLDI 2020)_. 1066–1082.
  * Raghavan et al. (2004) S. Raghavan, R. Rohana, D. Leon, A. Podgurski, and V. Augustine. 2004.  Dex: a semantic-graph differencing tool for studying changes in large code bases. In _20th IEEE International Conference on Software Maintenance, 2004. Proceedings._ 188–197.
  * Sassaman et al. (2013) Len Sassaman, Meredith L. Patterson, Sergey Bratus, and Michael E. Locasto. 2013.  Security Applications of Formal Language Theory.  _IEEE Systems Journal_ 7, 3 (2013), 489–500.
  * Schneeweisz (2020) Joern Schneeweisz. 2020\.  _How to exploit parser differentials_.  Retrieved July 16, 2021 from https://about.gitlab.com/blog/2020/03/30/how-to-exploit-parser-differentials/
  * Solar-Lezama (2008) Armando Solar-Lezama. 2008\.  _Program Synthesis by Sketching_.  Ph.D. Dissertation. UC Berkeley.
  * Stanford et al. (2021) Caleb Stanford, Margus Veanes, and Nikolaj Bjørner. 2021\.  Symbolic Boolean Derivatives for Efficiently Solving Extended Regular Expression Constraints. In _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ (Virtual, Canada) _(PLDI 2021)_. 620–635.
  * Thompson (1968) Ken Thompson. 1968\.  Programming techniques: Regular expression search algorithm.  _Commun. ACM_ 11, 6 (1968), 419–422.
  * Warth and Piumarta (2007) Alessandro Warth and Ian Piumarta. 2007.  OMeta: An Object-Oriented Language for Pattern Matching. In _Proceedings of the 2007 Symposium on Dynamic Languages_ (Montreal, Quebec, Canada) _(DLS ’07)_. 11–19.
  * Yu et al. (2019) Hao Yu, Wing Lam, Long Chen, Ge Li, Tao Xie, and Qianxiang Wang. 2019\.  Neural Detection of Semantic Code Clones via Tree-Based Convolution. In _Proceedings of the 27th International Conference on Program Comprehension_ (Montreal, Quebec, Canada) _(ICPC ’19)_. IEEE Press, 70–80.
  * Zeller et al. (2021) Andreas Zeller, Rahul Gopinath, Marcel Böhme, Gordon Fraser, and Christian Holler. 2021\.  _The Fuzzing Book_.  CISPA Helmholtz Center for Information Security.  https://www.fuzzingbook.org/ Retrieved 2021-03-12 11:41:11+01:00.


Xiaoyan Zhang (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
11institutetext:  School of Mathematical Science & Institute of Mathematics,
Nanjing Normal University, Nanjing 210023, P.R. China. 22institutetext: School
of Statistics & Mathematics, and Institute of Artificial Intelligence & Deep
Learning, Guangdong University of Finance & Economics, Guangzhou 510630, P.R.
China.

# Component factors in $K_{1,r}$-free graphs ††thanks: This work is supported
by the National Natural Science Foundation of China (Grant No. 11871280,
11971349 and U1811461), the Natural Science Foundation of Guangdong Province
(Grant No. 2020B1515310009) and Qinglan Project of Jiangsu Province.

Guowei Dai 11 Zanbo Zhang 22 Xiaoyan Zhang 11

###### Abstract

A graph is said to be $K_{1,r}$-free if it does not contain an induced
subgraph isomorphic to $K_{1,r}$. An $\mathcal{F}$-factor is a spanning
subgraph $H$ such that each connected component of $H$ is isomorphic to some
graph in $\mathcal{F}$. In particular, $H$ is called an
$\\{P_{2},P_{3}\\}$-factor of $G$ if $\mathcal{F}=\\{P_{2},P_{3}\\}$; $H$ is
called an $\mathcal{S}_{n}$-factor of $G$ if
$\mathcal{F}=\\{K_{1,1},K_{1,2},K_{1,3},...,K_{1,n}\\}$, where $n\geq 2$. A
spanning subgraph of a graph $G$ is called a $\mathcal{P}_{\geq k}$-factor of
$G$ if its each component is isomorphic to a path of order at least $k$, where
$k\geq 2$. A graph $G$ is called a $\mathcal{F}$-factor covered graph if there
is a $\mathcal{F}$-factor of $G$ including $e$ for any $e\in E(G)$. In this
paper, we give a minimum degree condition for a $K_{1,r}$-free graph to have
an $\mathcal{S}_{n}$-factor and a $\mathcal{P}_{\geq 3}$-factor, respectively.
Further, we obtain sufficient conditions for $K_{1,r}$-free graphs to be
$\mathcal{P}_{\geq 2}$-factor, $\mathcal{P}_{\geq 3}$-factor or
$\\{P_{2},P_{3}\\}$-factor covered graphs. In addition, examples show that our
results are sharp.

###### keywords:

minimum degree, $K_{1,r}$-free, $\mathcal{S}_{n}$-factor, $\mathcal{P}_{\geq
k}$-factor, $\mathcal{P}_{\geq k}$-factor covered graph.

Mathematics Subject Classification (2000) 05C70, 05C38

##  1 Introduction

We consider only finite simple graph, unless explicitly stated. We refer to
[Bondy1982] for the notation and terminologies not defined here. Let
$G=(V(G),E(G))$ be a simple graph, where $V(G)$ and $E(G)$ denote the vertex
set and the edge set of $G$, respectively. A subgraph $H$ of $G$ is called a
spanning subgraph of $G$ if $V(H)=V(G)$ and $E(H)\subseteq E(G)$. A subgraph
$H$ of $G$ is called an induced subgraph of $G$ if every pair of vertices in
$H$ which are adjacent in $G$ are also adjacent in $H$. For $v\in V(G)$, we
use $d_{G}(v)$ and $N_{G}(v)$ to denote the degree of $v$ and the set of
vertices adjacent to $v$ in $G$, respectively. For $S\subseteq V(G)$, we write
$N_{G}(S)=\cup_{v\in S}N_{G}(v)$. We use $\delta(G)$ to denote the minimum
degree of a graph $G$. We denote by $K_{m}$ the complete graph of order $m$.

A graph of order $r+1$ is called $K_{1,r}$ with center vertex $u$ if it has
the vertex set $\\{u,u_{1},u_{2},...,u_{r}\\}$ and edge set
$\\{uu_{1},uu_{2},...,uu_{r}\\}$, where $r$ is an integer with $r\geq 2$. We
use $S_{n}$ to denote the set $\\{K_{2},K_{1,2},K_{1,3},...,K_{1,n}\\}$, where
$n\geq 2$. For an integer $r\geq 3$, we say that a graph $G$ is $K_{1,r}$-free
if $G$ does not contain an induced subgraph isomorphic to $K_{1,r}$. In
particular, a graph is said to be claw-free if it is $K_{1,3}$-free.

For a family of connected graphs $\mathcal{F}$, a spanning subgraph $H$ of a
graph $G$ is called an $\mathcal{F}$-factor of $G$ if each component of $H$ is
isomorphic to some graph in $\mathcal{F}$. In particular, $H$ is called an
$\mathcal{S}_{n}$-factor of $G$ if
$\mathcal{F}=\\{K_{2},K_{1,2},K_{1,3},...,K_{1,n}\\}$. A spanning subgraph $H$
of a graph $G$ is called a $\mathcal{P}_{\geq k}$-factor of $G$ if every
component of $H$ is isomorphic to a path of order at least $k$. For example, a
$\mathcal{P}_{\geq 3}$-factor means a graph factor in which every component is
a path of order at least three. A graph $G$ is called a $\mathcal{P}_{\geq
k}$-factor covered graph if there is a $\mathcal{P}_{\geq k}$-factor of $G$
covering $e$ for any $e\in E(G)$.

Since Tutte proposed the well known Tutte 1-factor theorem [Tutte1952], there
are many results on graph factors [Akiyama1985, Amahashi1982, Egawa2018,
Kaneko2001, Wang1994], $\mathcal{S}_{n}$-factors [Egawa2008, Kano2010,
Kano2012, Yu1990], and $\mathcal{P}_{\geq k}$-factors in claw-free graphs and
cubic graphs [Ando2002, Kano2008, Kawarabayashi2002]. More results on graph
factors can be found in the survey papers and books in [Akiyama1985,
Plummer2007, Yu2009]. We use $\omega(G)$, $i(G)$ to denote the number of
components and isolated vertices of a graph $G$, respectively. For $X\subseteq
V(G)$, let $G[X]$ be the subgraph of $G$ induced by $X$ and define
$G-X:=G[V(G)-X]$. Akiyama, Avis and Era [Akiyama1980] proved the following
theorem, which is a criterion for a graph to have a $\mathcal{P}_{\geq
2}$-factor.

######  Theorem 1.1.

(Akiyama, Avis and Era [Akiyama1985]) A graph $G$ has a $\mathcal{P}_{\geq
2}$-factor if and only if $i(G-X)\leq 2|X|$ for all $X\subseteq V(G)$.

Amahashi, Kano [Amahashi1982] and Las Vergnas [Las1978] gave independently two
necessary and sufficient conditions for a graph to have an
$\mathcal{S}_{n}$-factor, which is a generalization of Theorem 1.1.

######  Theorem 1.2.

(Amahashi and Kano [Amahashi1982]; Las Vergnas [Las1978]) Let $n$ be an
integer with $n\geq 2$. Then a graph $G$ has an $\mathcal{S}_{n}$-factor if
and only if $i(G-X)\leq n|X|$ for all $X\subseteq V(G)$, or $|S|\leq
n|N_{G}(S)|$ for every independent set $S$ of $G$.

In this paper, we investigate the existence of $\mathcal{S}_{n}$-factors in
$K_{1,r}$-free graphs, and obtain a minimum degree condition for a
$K_{1,r}$-free graph to have an $\mathcal{S}_{n}$-factor as following.

######  Theorem 1.3.

Let $r,n$ be two integers with $r\geq 3$ and $n\geq 2$, and let $G$ be a
$K_{1,r}$-free graph. If
$\delta(G)\geq\left\lfloor\frac{r+n-2}{n}\right\rfloor$, then $G$ has an
$\mathcal{S}_{n}$-factor.

######  Remark 1.

The minimum degree condition in Theorem 1.3 is best possible. To see this, we
construct a graph $G=(r-1)K_{1}\vee G_{1}$, where $G_{1}\cong
K_{\left\lfloor\frac{r+n-2}{n}\right\rfloor-1}$ and $r\geq 3,n\geq 2$ are two
integers. It is obvious that
$\delta(G)=\left\lfloor\frac{r+n-2}{n}\right\rfloor-1$ and $G$ is
$K_{1,r}$-free. We choose $X=V(G_{1})$, and so
$|X|=\left\lfloor\frac{r+n-2}{n}\right\rfloor-1$. Thus, we have

$i(G-X)=r-1>n\times\left(\left\lfloor\frac{r+n-2}{n}\right\rfloor-1\right)=n|X|.$

In view of Theorem 1.10, $G$ has no $\mathcal{S}_{n}$-factor.

Since the graph $P_{k},~{}k\geq 4$ itself has a $\\{P_{2},P_{3}\\}$-factor, it
is easy to verify that a graph has a $\mathcal{P}_{\geq 2}$-factor if and only
if it has a $\\{K_{2},K_{1,2}\\}$-factor. Let $n=2$, then by Theorem 1.3, we
can obtain the the following corollary immediately.

######  Corollary 2.

Let $r$ be an integer with $r\geq 3$, and let $G$ be a $K_{1,r}$-free graph.
If $\delta(G)\geq\left\lfloor\frac{r}{2}\right\rfloor$, then $G$ has a
$\mathcal{P}_{\geq 2}$-factor.

Kaneko [Kaneko2003] introduced the concept of a sun and gave a
characterization for a graph with a $\mathcal{P}_{\geq 3}$-factor. It is
perhaps the first characterization of graphs which have a path factor not
including $P_{2}$. Recently, Kano et al. [Kano2004] presented a simpler proof
for Kaneko’s theorem [Kaneko2003].

A graph $H$ is called factor-critical if $H-\\{v\\}$ has a 1-factor for each
$v\in V(H)$. Let $H$ be a factor-critical graph and
$V(H)=\\{v_{1},v_{2},...,v_{n}\\}$. By adding new vertices
$\\{u_{1},u_{2},...,u_{n}\\}$ together with new edges $\\{v_{i}u_{i}:1\leq
i\leq n\\}$ to $H$, the resulting graph is called a sun. Note that, according
to Kaneko [Kaneko2003], we regard $K_{1}$ and $K_{2}$ also as a sun,
respectively. Usually, the suns other than $K_{1}$ are called big suns. It is
called a sun component of $G-X$ if the component of $G-X$ is isomorphic to a
sun. We denote by $sun(G-X)$ the number of sun components in $G-X$.

######  Theorem 1.4.

(Kaneko [Kaneko2003]) A graph $G$ has a $\mathcal{P}_{\geq 3}$-factor if and
only if $sun(G-X)\leq 2|X|$ for all $X\subseteq V(G)$.

From Theorem 1.4, Kaneko [Kaneko2003] immediately deduce the following
corollary.

######  Corollary 3.

(Kaneko [Kaneko2003]) Every claw-free graph with minimum degree at least 2 has
a $\mathcal{P}_{\geq 3}$-factor.

We extend Corollary 3 and obtain a minimum degree condition for a
$K_{1,r}$-free graph admitting a $\mathcal{P}_{\geq 3}$-factor.

######  Theorem 1.5.

Let $r$ be an integer with $r\geq 3$, and let $G$ be a $K_{1,r}$-free graph.
If $\delta(G)\geq\left\lfloor\frac{r}{2}\right\rfloor+1$, then $G$ has a
$\mathcal{P}_{\geq 3}$-factor.

######  Remark 4.

The minimum degree condition in Theorem 1.5 is best possible. To see this, we
construct a graph $G=(r-1)K_{2}\vee
K_{\left\lfloor\frac{r}{2}\right\rfloor-1}$, where $r\geq 3$ is an integer. It
is obvious that $\delta(G)=\left\lfloor\frac{r}{2}\right\rfloor$ and $G$ is
$K_{1,r}$-free. We choose $X=V(K_{\left\lfloor\frac{r}{2}\right\rfloor-1})$,
and so $|X|=\left\lfloor\frac{r}{2}\right\rfloor-1$. Thus, we have

$sun(G-X)=r-1>2\times\left(\left\lfloor\frac{r}{2}\right\rfloor-1\right)=2|X|.$

In view of Theorem 1.4, $G$ has no $\mathcal{P}_{\geq 3}$-factor.

Zhang and Zhou [Zhang2009] proposed the concept of path-factor covered graphs,
which is a generalization of matching covered graphs. They also obtained a
characterization for $\mathcal{P}_{\geq 2}$-factor and $\mathcal{P}_{\geq
3}$-factor covered graphs, respectively.

######  Theorem 1.6.

(Zhang et al. [Zhang2009]) Let $G$ be a connected graph. Then $G$ is a
$\mathcal{P}_{\geq 2}$-factor covered graph if and only if $i(G-S)\leq
2|S|-\varepsilon_{1}(S)$ for all $S\subseteq V(G)$, where $\varepsilon_{1}(S)$
is defined by

$\varepsilon_{1}(S)=\begin{cases}2\quad\ \
&if~{}S\neq\emptyset~{}and~{}S~{}is~{}not~{}an~{}independent~{}set;\\\ 1\quad\
\ &if~{}S~{}is~{}a~{}nonempty~{}independent~{}set~{}and~{}there~{}exists\\\
~{}\quad\ \ &a~{}nontrivial~{}component~{}of~{}$G$-$S$;\\\ 0\quad\ \
&otherwise.\end{cases}$

######  Theorem 1.7.

(Zhang et al. [Zhang2009]) Let $G$ be a connected graph. Then $G$ is a
$\mathcal{P}_{\geq 3}$-factor covered graph if and only if $sun(G-S)\leq
2|S|-\varepsilon_{2}(S)$ for all $S\subseteq V(G)$, where $\varepsilon_{2}(S)$
is defined by

$\varepsilon_{2}(S)=\begin{cases}2\quad\ \
&if~{}S\neq\emptyset~{}and~{}S~{}is~{}not~{}an~{}independent~{}set;\\\ 1\quad\
\
&if~{}S~{}is~{}a~{}nonempty~{}independent~{}set~{}and~{}there~{}exists~{}a\\\
~{}\quad\ \ &non-sun~{}component~{}of~{}$G$-$S$;\\\ 0\quad\ \
&otherwise.\end{cases}$

The first author of this paper has verified that a claw-free graph $G$ is a
$\mathcal{P}_{\geq 2}$-factor covered graph if $\delta(G)\geq 2$ [Dai]. We
extend the above result and obtain a minimum degree condition for a
$K_{1,r}$-free graph being a $\mathcal{P}_{\geq 2}$-factor covered graph.

######  Theorem 1.8.

Let $r$ be an integer with $r\geq 3$, and let $G$ be a $K_{1,r}$-free graph.
If $\delta(G)\geq\left\lfloor\frac{r}{2}\right\rfloor+1$, then $G$ is a
$\mathcal{P}_{\geq 2}$-factor covered graph.

######  Remark 5.

The minimum degree condition in Theorem 1.8 is best possible. In order to show
this, we construct a graph $G=(r-1)K_{1}\vee
K_{\left\lfloor\frac{r}{2}\right\rfloor}$, where $r\geq 3$ is an integer. It
is obvious that $\delta(G)=\left\lfloor\frac{r}{2}\right\rfloor$ and $G$ is
$K_{1,r}$-free. We choose $S=V(K_{\left\lfloor\frac{r}{2}\right\rfloor})$, and
so $|S|=\left\lfloor\frac{r}{2}\right\rfloor$. Note that
$\varepsilon_{1}(S)=2$. Thus, we have

$i(G-S)=r-1>2\times\left\lfloor\frac{r}{2}\right\rfloor-2=2|S|-\varepsilon_{1}(S).$

In terms of Theorem 1.6, $G$ is not a $\mathcal{P}_{\geq 2}$-factor covered
graph.

The first author of this paper has also verified that a claw-free graph $G$ is
a $\mathcal{P}_{\geq 3}$-factor covered graph if $\delta(G)\geq 3$ [Dai]. We
extend the above result and obtain a minimum degree condition for a
$K_{1,r}$-free graph being a $\mathcal{P}_{\geq 3}$-factor covered graph.

######  Theorem 1.9.

Let $r$ be an integer with $r\geq 3$, and let $G$ be a $K_{1,r}$-free graph.
If $\delta(G)\geq\left\lfloor\frac{r}{2}\right\rfloor+2$, then $G$ is a
$\mathcal{P}_{\geq 3}$-factor covered graph.

######  Remark 6.

The minimum degree condition in Theorem 1.9 is best possible. In order to show
this, we construct a graph $G=(r-1)K_{2}\vee
K_{\left\lfloor\frac{r}{2}\right\rfloor}$, where $r\geq 3$ is an integer. It
is obvious that $\delta(G)=\left\lfloor\frac{r}{2}\right\rfloor+1$ and $G$ is
$K_{1,r}$-free. We choose $S=V(K_{\left\lfloor\frac{r}{2}\right\rfloor})$, and
so $|S|=\left\lfloor\frac{r}{2}\right\rfloor$. Note that
$\varepsilon_{2}(S)=2$. Thus, we have

$sun(G-S)=r-1>2\times\left\lfloor\frac{r}{2}\right\rfloor-2=2|S|-\varepsilon_{2}(S).$

In terms of Theorem 1.7, $G$ is not a $\mathcal{P}_{\geq 3}$-factor covered
graph.

Let $n=2$, then $\mathcal{S}_{n}=\\{P_{2},P_{3}\\}$. The following is a main
result in [Yu1991] and [Yu1987].

######  Theorem 1.10.

Let $G$ be a connected graph. $G$ is a $\\{P_{2},P_{3}\\}$-factor covered
graph if and only if $i(G-S)\leq 2|S|-\varepsilon_{3}(S)$ for all $S\subseteq
V(G)$, where $\varepsilon_{3}(S)$ is defined by

$\varepsilon_{3}(S)=\begin{cases}3\quad\ \
&if~{}nonempty~{}set~{}X~{}is~{}not~{}independent;\\\ 0\quad\ \
&otherwise.\end{cases}$

Note that a graph is a $\mathcal{P}_{\geq 2}$-factor covered graph not
equivalent to a $\\{P_{2},P_{3}\\}$-factor covered graph. For example,
$P:=x_{1}x_{2}x_{3}x_{4}$ is a $\mathcal{P}_{\geq 2}$-factor covered graph and
it has no $\\{P_{2},P_{3}\\}$-factor to cover edge $x_{2}x_{3}$. We give a
sufficient condition for a $K_{1,r}$-free graph to be a
$\\{P_{2},P_{3}\\}$-factor covered graph.

######  Theorem 1.11.

Let $r$ be an integer with $r\geq 3$, and let $G$ be a $K_{1,r}$-free graph.
If $\delta(G)\geq\left\lceil\frac{r}{2}\right\rceil+1$, then $G$ is a
$\\{P_{2},P_{3}\\}$-factor covered graph.

######  Remark 7.

The minimum degree condition in Theorem 1.11 is best possible. In order to
show this, we construct a graph $G=(r-1)K_{1}\vee
K_{\left\lceil\frac{r}{2}\right\rceil}$, where $r\geq 3$ is an integer. It is
obvious that $\delta(G)=\left\lceil\frac{r}{2}\right\rceil$ and $G$ is
$K_{1,r}$-free. We choose $S=V(K_{\left\lceil\frac{r}{2}\right\rceil})$, and
so $|S|=\left\lceil\frac{r}{2}\right\rceil$. Note that $\varepsilon_{3}(S)=3$.
Thus, we have

$i(G-S)=r-1>2\times\left\lceil\frac{r}{2}\right\rceil-3=2|S|-\varepsilon_{3}(S).$

In terms of Theorem 1.10, $G$ is not a $\\{P_{2},P_{3}\\}$-factor covered
graph.

##  2 Proof of Theorem 1.3

By contradiction, suppose that Theorem 1.3 is not hold. Then, there exists a
$K_{1,r}$-free graph $G$ such that
$\delta(G)\geq\left\lfloor\frac{r+n-2}{n}\right\rfloor$, and $G$ has no
$\mathcal{S}_{n}$-factor. It is easy to find that $G$ has a connected
component $G^{\prime}$ such that $G^{\prime}$ has no $\mathcal{S}_{n}$-factor.
Note that $G^{\prime}$ is also a $K_{1,r}$-free graph and
$\delta(G^{\prime})\geq\left\lfloor\frac{r+n-2}{n}\right\rfloor\geq 1$. By
Theorem 1.10, there exists a subset $X\subseteq V(G^{\prime})$ such that
$i(G^{\prime}-X)>n|X|$. In terms of the integrality of $i(G^{\prime}-X)$, we
obtain that

$i(G^{\prime}-X)\geq n|X|+1.$ (1)

###### Claim 2.1

$X\neq\emptyset$.

######  Proof 2.1.

Suppose $X=\emptyset$, then $i(G^{\prime})=i(G^{\prime}-X)\geq n|X|+1=1$.
Since $G^{\prime}$ is a connected graph, we obtain that $G^{\prime}$ is a
isolated vertex, which contradicts the minimum degree of $G^{\prime}$. This
completes the proof of Claim 2.1. ∎

By Claim 2.1, $X\neq\emptyset$. Let $X=\\{x_{1},x_{2},...,x_{k}\\}$, then
$|X|=k$. Let $Y=\\{y_{1},y_{2},\ldots,y_{m}\\}$ be the set of isolated
vertices of $G^{\prime}-X$. Then, by (1), we have that

$i(G^{\prime}-X)=m\geq nk+1.$ (2)

Next, we construct a bipartite subgraph $F$ of $G^{\prime}$ such that
$V(F)=V(X)\cup V(Y)$ and $x_{i}y_{j}\in E(F)$ if and only if $x_{i}y_{j}\in
E(G^{\prime})$ for any $i\in[1,k],~{}j\in[1,m]$. Since
$\delta(G^{\prime})\geq\left\lfloor\frac{r+n-2}{n}\right\rfloor$, we have
$d_{X}(y_{j})\geq\left\lfloor\frac{r+n-2}{n}\right\rfloor$ for any
$j\in[1,m]$. By (2), we can derive that

$|X|\geq d_{X}(y_{j})\geq\left\lfloor\frac{r+n-2}{n}\right\rfloor,$

and thus

$\displaystyle|E(F)|$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{m}d_{F}(y_{j})$ $\displaystyle\geq$ $\displaystyle
m\times\left\lfloor\frac{r+n-2}{n}\right\rfloor$ $\displaystyle\geq$
$\displaystyle(nk+1)\times\frac{r-1}{n}$ $\displaystyle=$ $\displaystyle
kr+\frac{r-1}{n}.$

It follows immediately that

$\frac{|E(F)|}{|X|}\geq\frac{k(r-1)+\frac{r-1}{n}}{k}=r-1+\frac{r-1}{nk}>r-1.$
(3)

By pigeonhole principle and (3), there exists $x_{i}\in X$ such that
$d_{F}(x_{i})\geq r$. Let $J=N_{F}(x_{i})\cap Y$, then
$G^{\prime}[\\{x_{i}\\}\cup J]\cong K_{1,|J|}$. Since $G^{\prime}$ is
$K_{1,r}$-free, $|J|<r$, which is a contradiction to that
$|J|=d_{F}(x_{i})\geq r$.

This completes the proof of Theorem 1.3.

##  3 Proof of Theorem 1.5

By contradiction, suppose that Theorem 1.5 is not hold. Then, there exists a
$K_{1,r}$-free graph $G$ such that
$\delta(G)\geq\left\lfloor\frac{r}{2}\right\rfloor+1$, and $G$ has no
$\mathcal{P}_{\geq 3}$-factor. It is easy to find that $G$ has a connected
component $G^{\prime}$ such that $G^{\prime}$ has no $\mathcal{P}_{\geq
3}$-factor. Note that $G^{\prime}$ is also a $K_{1,r}$-free graph and
$\delta(G^{\prime})\geq\left\lfloor\frac{r}{2}\right\rfloor+1\geq 2$. By
Theorem 1.4, there exists a subset $X\subseteq V(G^{\prime})$ such that
$sun(G^{\prime}-X)>2|X|$. In terms of the integrality of $sun(G^{\prime}-X)$,
we obtain that

$sun(G^{\prime}-X)\geq 2|X|+1.$ (4)

###### Claim 3.1

$X\neq\emptyset$.