Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 17 of 17 for “"context-free language"”.
-
Some aspects of error correction of programming languages
… treats the problem of error correction in a context free language, and the design of an error correcting parser for the BASIC language. Two important things can be said about this thesis. First, it presents the problem of error correction in a context free language, and the existing results …
-
Improving the Efficiency of Graph-Based Static Analysis
… of three popular static analysis frameworks: context-free language reachability, recursive state machine reachability and set constraint analysis. In this dissertation, the methodologies focus more on eliminating redundancy rather than theoretically lowering complexity. For transitive …
-
Distances Between Languages: Algorithms and Descriptional Complexity
… 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 …
-
An algorithm for error correction in context-free languages
… that corrects three common spelling errors in a context-free language and then describes an implementation on a digital computer.</p><p>The algorithm described initially applies transformations to the original grammar to produce three new grammars. Each new grammar will generate the strings in …
-
A YACC implementation for a PL/M interpreter
… error handler, and execution phase. The language defined in PINYIM is a context-free language. Upon giving the grammar rules YACC produces a bottom-up LALR(1) parser. Quadruple codes are used as intermediate codes in PINYIM. These quadruple codes are executed directly if there is no error …
-
Efficient points-to analysis based on CFL-reachability summarisation
… more efficient points-to analysis based on Context-Free Language (CFL)-reachability. In general, our techniques significantly improve the state-of-the-art points-to analysis for Java applications when handling demand-driven queries and small code changes. This thesis firstly presents an …
-
Design, implementation and testing of a common data model supporting autonomous vehicle compatibility and interoperability
… arbitrary vehicles using the Extensible Markup Language (XML). An exemplar, the Autonomous Vehicle Command Language (AVCL), encapsulates behavior-scripted mission definition, goalbased mission definition, inter-vehicle communication, and mission results. Broad applicability is obtained through …
-
Precision-Preserving Acceleration of Object-Sensitive Pointer Analysis with CFL-Reachability
Object-sensitivity is widely used as a context abstraction for computing the points-to information context-sensitively for object-oriented languages like Java. Due to the combinatorial explosion of contexts in large programs, k-object-sensitive pointer analysis (under k-limiting), k-obj, is …
-
Succinct function representations for simulation and verification
… representations. Toward this goal, we propose Context-Free-Language Ordered Binary Decision Diagrams (CFLOBDDs), which can represent Boolean functions exponentially more succinctly than BDDs, and double-exponentially more succinctly than decision trees, in the best case. They have the potential …
-
Counting Flimsy Numbers via Formal Language Theory
… the k-flimsy base-b numbers. Using the tools of context-free languages and analytic combinatorics, we use this automaton to determine precise asymptotics for the number of k-flimsy N-digit numbers in base b. Lastly, using the results we obtained, we discuss the natural densities of k-flimsy …
-
Complexity of Dyck-reachability in directed graphs
… edge labels of the path is a member of the Dyck language, i.e., the language of balanced parentheses. We present previous works on upper bounds in Dyck-reachability in graphs and the equivalent formulation of the problem in the context of Recursive State Machines. We also present known lower …
-
Epsilon Precedence Grammars and Languages
… with at most one ε-rule, ESP1, define a class of languages which properly includes the class of ESP0 languages, but is itself properly included in the class of deterministic, context-free languages. In general, ESP grammars having at most i ε-rules, ESPi, define a class of languages which is …
-
Rethinking Verification as Structured Search: Applications to Neural Network Verification and Static Analysis
… that key reachability problems, including context-free-language reachability and set-constraint analysis, can achieve provably faster asymptotic complexity under standard quantum assumptions. Overall, these contributions demonstrate that improving search efficiency in graph-based …
-
SCAN: ΜΙΑ ΓΛΩΣΣΑ ΓΙΑ ΑΚΟΛΟΥΘΙΑΚΗ ΠΡΟΣΠΕΛΑΣΗ ΔΙΔΙΑΣΤΑΤΩΝ ΔΕΔΟΜΕΝΩΝ
… AND THE DEVELOPMENT OF A NEW, SPECIAL PURPOSE LANGUAGE, CALLED SCAN LANGUAGE. THE DEVELOPMENT OF SCAN PROVIDES AN EFFICIENT APPROACH TO THE FOLLOWING PROBLEM: "GIVEN AN IMAGE ARRAY P OFNXN ELEMENTS, DEVELOP A TOOL WHICH CAN DESCRIBE AND PRODUCE ALL POSSIBLE SCANNING SEQUENCES OF P (THAT IS …
-
A Lightweight Framework for Universal Fragment Composition
Domain-specific languages (DSLs) are useful tools for coping with complexity in software development. DSLs provide developers with appropriate constructs for specifying and solving the problems they are faced with. While the exact definition of DSLs can vary, they can roughly be divided into two …
-
DESCRIPTIONAL COMPLEXITY AND PARIKH EQUIVALENCE
… deals with some topics in the theory of formal languages and automata. Specifically, the thesis deals with the theory of context-free languages and the study of their descriptional complexity. The descriptional complexity of a formal structure (e.g., grammar, model of automata, etc) is the …