Computing, School ofhttp://hdl.handle.net/1974/7712017-08-23T23:22:47Z2017-08-23T23:22:47ZDistances Between Languages: Algorithms and Descriptional ComplexityNg, Timothyhttp://hdl.handle.net/1974/220182017-08-22T19:23:38ZDistances Between Languages: Algorithms and Descriptional Complexity
Ng, Timothy
We consider the descriptional complexity of neighbourhoods of regular languages and the computational complexity of computing the distance between languages. Distance measures are defined on words to describe their similarity. These measures can be extended to languages, which are sets of words. We consider several different notions of distance measures on languages.
The neighbourhood of a language L is the set of words within some fixed distance of a word in L. We show that we can construct weighted finite automata for neighbourhoods of regular languages with respect to additive quasi-distances. We consider the state complexity of the neighbourhoods and the state complexity of approximate pattern matching. We establish a tight state complexity lower bound for the edit distance neighbourhood of a language recognized by a deterministic finite automaton.
We consider the deterministic and nondeterministic state complexity of prefix, suffix, and subword distance neighbourhoods. We establish tight deterministic state complexity bounds for the prefix and suffix distance neighbourhoods of regular languages and of finite languages. For prefix distance neighbourhoods, we consider prefix-convex subclasses of regular languages. We also establish the state complexity of suffix neighbourhoods of suffix-closed languages. We give an upper bound for the state complexity of the subword distance neighbourhood of a regular language.
Based on the edit distance algorithms of Mohri and Han and co-authors, we give algorithms for computing the prefix distance between two regular languages, a context-free language and a regular language, and two visibly pushdown languages. We extend these algorithms to compute the inner prefix distance of regular languages and visibly pushdown languages.
We give algorithms to compute the relative prefix distance of two regular languages. For a given integer k, we show that for a deterministic context-free language and a regular language or for two visibly pushdown languages, it is decidable whether their relative prefix distance is at most k. This is very close to the borderline between decidable and undecidable since, on the other hand, we show that deciding the same question for a deterministic context-free language and a visibly pushdown language is undecidable.
Discovery of Patterns in Simulink Systemsde la Parra, Franciscohttp://hdl.handle.net/1974/201022017-08-10T12:20:27ZDiscovery of Patterns in Simulink Systems
de la Parra, Francisco
Model-Driven Engineering tools and techniques have become mainstream aids in the development
of embedded cyber-physical systems. The large-scale use of visual models is a powerful
paradigm for designing reliable and maintainable systems assembled with complex hardware, software
and mechanical elements. Modular design approaches can readily capture the requirements
for embedded systems into executable and evolutionary models.
We propose a framework to discover, classify and visualize model-patterns in large repositories of
Simulink models. We design, and implement in a software toolchain, a set of scalable algorithms to
fully traverse and contextually parse the source code of these repositories in order to compute topology
hash functions for the size, name connectivity and type connectivity of each model subsystem,
as well as properties of Stateflow charts. We use these extracted properties to cluster the subsystems
into a set of addressable-by-property classes. We develop an interactive model visualization and
querying facility, embodied by the MoSART user interface, to identify further relations, similarities
and abstractions in the elements of the cluster classes. This tool provides a configurable environment
for inferring structural model-patterns and elaborating on semantic model-patterns with the assistance
of skilled domain knowledge. We propose a query system, based on regular expressions that
match values of previously computed subsystems properties, as an effective method to iteratively
refine Simulink model-patterns abstractions into accumulated modeling knowledge.
Our implementation works cooperatively with a 3-phase iterative model-pattern discovery approach
that we conceptualize as 1) model clustering: repository traversal and subsystem-topology
evaluation for clustering subsystems, 2) primary model-pattern inference: visualization, querybased
search and clustering for identifying basic semantic patterns, 3) model-pattern refinement:
continuous refinement of basic patterns into specialized groups for application in targeted use cases.
We effectively support the iterative nature of this approach because our repository traversal, property
evaluation and clustering algorithms have low time-complexity, that is, between a lower-bound(n) and
O(n lg n)(n = total lines of source code in a repository), and our interactive tool provides a
complete-coverage view of a model repository.
State complexity of deletion and bipolar deletionHan, Yo-SubKo, Sang-KiSalomaa, Kaihttp://hdl.handle.net/1974/159612017-07-18T07:14:52Z2016-01-01T00:00:00ZState complexity of deletion and bipolar deletion
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai
It is well known that the language obtained
by deleting an arbitrary
language from a regular language is regular.
We give an upper bound for the
state complexity of deleting an arbitrary
language from a regular language and a matching
lower bound.
We show that the state complexity of deletion
is $n \cdot 2^{n-1}$ (respectively, $(n + \frac{1}{2}) \cdot 2^n - 2$)
when using complete (respectively, incomplete) deterministic
finite automata.
We show that the state complexity of bipolar deletion
has an upper bound $n^n$ (respectively $(n+1)^n - 1$)
when using complete (respectively, incomplete)
deterministic finite automata. In both cases we give
almost matching lower bounds.
2016-01-01T00:00:00ZDescriptional complexity of unambiguous input-driven pushdown automataOkhotin, AlexanderSalomaa, Kaihttp://hdl.handle.net/1974/159602017-07-18T07:14:50Z2015-04-01T00:00:00ZDescriptional complexity of unambiguous input-driven pushdown automata
Okhotin, Alexander; Salomaa, Kai
It is known that
a nondeterministic input-driven pushdown automaton (IDPDA)
(a.k.a.~visibly pushdown automaton;
a.k.a.~nested word automaton) of size $n$
can be transformed to an equivalent deterministic automaton
of size $2^{\Theta(n^2)}$
(B. von Braunm\"uhl, R. Verbeek,
\href{http://dx.doi.org/10.1016/S0304-0208(08)73072-X}
{``Input-driven languages are recognized in $\log n$ space''},
FCT 1983),
and that this size is necessary in the worst case
(R. Alur, P. Madhusudan,
\href{http://dx.doi.org/10.1145/1516512.1516518}
{``Adding nesting structure to words''},
J.ACM, 2009).
This paper demonstrates
that the same worst-case $2^{\Theta(n^2)}$ size blow-up
occurs when converting
a nondeterministic IDPDA to an unambiguous one,
and an unambiguous IDPDA to a deterministic one.
In addition, the methods developed in this paper
are used to demonstrate
that the descriptional complexity of complementation
for nondeterministic IDPDAs
is $2^{\Theta(n^2)}$,
and that the descriptional complexity of homomorphisms
for deterministic IDPDAs
is $2^{\Theta(n^2)}$ as well.
2015-04-01T00:00:00Z