To see the other types of publications on this topic, follow the link: Regular expressions and languages.
Dissertations / Theses on the topic 'Regular expressions and languages'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Regular expressions and languages.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Andersson, Adam, and Ludwig Hansson. "Modernizing the Syntax of Regular Expressions." Thesis, Blekinge Tekniska Högskola, Institutionen för programvaruteknik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-19895.
Full textAbstract:
Context Writing and working with regular expressions could be a slow and tedious task,which is mainly because of its syntax, but also because there exist several different dialectswhich easily could cause confusion. Even though regular expression has been widely used forparsing and programming language design, they are now frequently used for input validationand seen in common applications such as text editors. Objectives The main objectives of our thesis are to determine whether or not a regularexpression language that is more like the surrounding programming language would increaseusability, readability, and maintainability. We will then investigate further into what kind ofimpact this would have regarding e.g, development speed, and what benefits and liabilities amore modernized syntax could introduce. Methods Two different methods were used to answer our research questions, exploratory in-terviews, and experiments. The data from the experiments were collected by screen recordingand a program in the environment we provided to the participant. Results.By doing interviews with developers that use traditional regular expressions on aregular basis, their stories confirm that its syntax is confusing even for developers with alot of experience. Our results from the experiment indicate that a language more like thesurrounding language increases both the overall ease of use and development speed. Conclusions From this research, we can conclude that a regular expression language thatis more like the surrounding programming language does increase usability, readability, andmaintainability. We could clearly see that it had a positive effect on the development speed aswell. Keywords — regular expressions, programming language design, readability
2
Miklarz, Clément. "Etude d'extensions des langages déterministes." Thesis, Normandie, 2019. http://www.theses.fr/2019NORMR059/document.
Full textAbstract:
Cette thèse a pour but d’étudier des propriétés structurelles d’automates étendant celle du déterminisme, et les langages pouvant être dénotés par une expression rationnelle dont l’automate des positions présente l’une de ces propriétés. Si Book et al. ont montré que tous les langages rationnels peuvent être reconnus par un automate des positions non-ambigu, Brüggemann-Klein et Wood ont montré que ceux pouvant l’être par un automate des positions déterministe forment une famille strictement incluse dans celle des rationnels. Nous nous intéressons aux extensions de cette famille, en cherchant à caractériser leurs langages, et à étudier leur hiérarchie interne et leur inclusion entre elles<br>This thesis aims to study structural properties of automata extending determinism, and the languages that can be denoted by a regular expression of which the position automaton has one such property. If Book et al. showed that all regular languages can be recognized by an unambiguous position automaton, Brüggemann-Klein and Wood showed that only a proper subset of them can be recognized by a deterministic position automaton. We focus on extensions of this subfamily, by seeking to characterize their languages, and to study their internal hierarchy and how they relate to each other
3
Teichmann, Markus. "Expressing Context-Free Tree Languages by Regular Tree Grammars." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-224756.
Full textAbstract:
In this thesis, three methods are investigated to express context-free tree languages by regular tree grammars. The first method is a characterization. We show restrictions to context-free tree grammars such that, for each restricted context-free tree grammar, a regular tree grammar can be constructed that induces the same tree language. The other two methods are approximations. An arbitrary context-free tree language can be approximated by a regular tree grammar with a restricted pushdown storage. Furthermore, we approximate weighted context-free tree languages, induced by weighted linear nondeleting context-free tree grammars, by showing how to approximate optimal weights for weighted regular tree grammars.
4
Chandrasekhar, Muthyala. "Area efficient PLA's for the recognition of regular expression languages." Thesis, McGill University, 1985. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=65399.
Full text
5
Aljaloud, Saud. "An investigation into the performance of regular expressions within SPARQL query language." Thesis, University of Southampton, 2019. https://eprints.soton.ac.uk/428044/.
Full textAbstract:
SPARQL has not simply been the standard querying language for the Resource Description Framework (RDF) within the Semantic Web, but it has also gradually become one of the main querying languages for the graph model, in general. To be able to process SPARQL in a more efficient manner, an RDF store (as a DBMS) has to be used. However, SPARQL faces huge performance challenges for various reasons: the high exibility of RDF model, the fact that the SPARQL standardisation does not always focus on the performance side, or the immaturity of RDF and SPARQL in comparison to some other models such as SQL. One of SPARQL features is the ability to search through literals/strings by using a Regular Expression (Regex) filter. This adds a very handy and expressive utility, which allows users to search through strings or filter certain URIs. However, Regex is computationally expensive as well as resource intensive in that, for example, data has to be loaded into the memory. This thesis aims to investigate the performance of Regex within SPARQL. Firstly, we propose an analysis of the way people use Regex within SPARQL by looking at a huge log of queries made available provided by various RDF store providers. The analysis indicates various use cases in which their performance can be made more efficient. There is very little in the literature to adequately test the performance of Regex within SPARQL. We also propose the first Regex-Specic benchmark, named (BSBMstr) to be applied to the area of SPARQL. BSBMstr shows how various Regex features affect the overall performance of the SPARQL queries. BSBMstr also reports its results on seven known RDF stores. SPARQL benchmarks, in general, have been a major eld that attracts much research in the area of the Semantic Web. Nevertheless, many have argued that there are still issues in their design or simulation of real-world scenarios. This thesis also proposes a generic SPARQL benchmark, named CBSBench which introduces a new design of benchmarks. Unlike other benchmarks, CBSBench measures the performance of clusters rather than fixed queries. The usage of clusters also provides a stress test on RDF stores, because of the diversity of queries within each cluster. the CBSBench results are also reported on very different RDF stores. Finally, the thesis introduces (RegjInd)ex which is a Regex index data structure that is based on a tri-grams inverted index. This index aims to reduce the result sets to be scanned to match a Regex filter within SPARQL. The proposal has been evaluated by two different Regex-specic benchmarks and implemented on top of two RDF stores. (RegjInd)ex produces a smaller index size compared to previous work, while still being able to produce results faster than the original implementations by up to an order of magnitude. In general, the thesis provide a general guidelines that can be followed by developers to investigate similar features within a given DBMS. The investigation mainly relies on real-world usage by analysing how people are using these features. From that analysis, developers can construct queries and features alongside our proposed benchmarks to run tests on their chosen subject. The thesis also discusses various ideas and techniques that can be used to enhance the performance of DBMSs.
6
Memeti, Suejb. "Automatic Java Code Generator for Regular Expressions and Finite Automata." Thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-20486.
Full text
7
Fransson, Tobias. "Simulators for formal languages, automata and theory of computation with focus on JFLAP." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-18351.
Full textAbstract:
This report discusses simulators in automata theory and which one should be best for use in laboratory assignments. Currently, the Formal Languages, Automata and Theory of Computation course (FABER) at Mälardalen University uses the JFLAP simulator for extra exercises. To see if any other simulators would be useful either along with JFLAP or standalone, tests were made with nine programs that are able to graphically simulate automata and formal languages. This thesis work started by making an overview of simulators currently available.After the reviews it has become clear to the author that JFLAP is the best choice for majority of cases. JFLAP is also the most popular simulator in automata theory courses worldwide.To support the use of JFLAP for the course a manual and course assignments are created to help the student to getting started with JFLAP. The assignments are expected to replace the current material in the FABER course and to help the uninitiated user to get more out of JFLAP.
8
Ulus, Dogan. "Pattern Matching with Time : Theory and Applications." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM003/document.
Full textAbstract:
Les systèmes dynamiques présentent des comportements temporels qui peuvent être exprimés sous diverses formes séquentielles telles que des signaux, des ondes, des séries chronologiques et des suites d'événements. Détecter des motifs sur de tels comportements temporels est une tâche fondamentale pour comprendre et évaluer ces systèmes. Étant donné que de nombreux comportements du système impliquent certaines caractéristiques temporelles, le besoin de spécifier et de détecter des motifs de comportements qui implique des exigences de synchronisation, appelées motifs temporisés, est évidente.Cependant, il s'agit d'une tâche non triviale due à un certain nombre de raisons, notamment la concomitance des sous-systèmes et la densité de temps.La contribution principale de cette thèse est l'introduction et le développement du filtrage par motif temporisé, c'est-à-dire l'identification des segments d'un comportement donné qui satisfont un motif temporisé. Nous proposons des expressions rationnelles temporisées (TRE) et la logique de la boussole métrique (MCL) comme langages de spécification pour motifs temporisés. Nous développons d'abord un nouveau cadre qui abstraite le calcul des aspects liés au temps appelé l'algèbre des relations temporisées. Ensuite, nous fournissons des algorithmes du filtrage hors ligne pour TRE et MCL sur des comportements à temps dense à valeurs discrètes en utilisant ce cadre et étudions quelques extensions pratiques.Il est nécessaire pour certains domaines d'application tels que le contrôle réactif que le filtrage par motif doit être effectué pendant l'exécution réelle du système. Pour cela, nous fournissons un algorithme du filtrage en ligne pour TREs basé sur la technique classique des dérivées d'expressions rationnelles. Nous croyons que la technique sous-jacente qui combine les dérivées et les relations temporisées constitue une autre contribution conceptuelle majeure pour la recherche sur les systèmes temporisés.Nous présentons un logiciel libre Montre qui implémente nos idées et algorithmes. Nous explorons diverses applications du filtrage par motif temporisé par l'intermédiaire de plusieurs études de cas. Enfin, nous discutons des orientations futures et plusieurs questions ouvertes qui ont émergé à la suite de cette thèse<br>Dynamical systems exhibit temporal behaviors that can be expressed in various sequential forms such as signals, waveforms, time series, and event sequences. Detecting patterns over such temporal behaviors is a fundamental task for understanding and assessing these systems. Since many system behaviors involve certain timing characteristics, the need to specify and detect patterns of behaviors that involves timing requirements, called timed patterns, is evident. However, this is a non-trivial task due to a number of reasons including the concurrency of subsystems and density of time.The key contribution of this thesis is in introducing and developing emph{timed pattern matching}, that is, the act of identifying segments of a given behavior that satisfy a timed pattern. We propose timed regular expressions (TREs) and metric compass logic (MCL) as timed pattern specification languages. We first develop a novel framework that abstracts the computation of time-related aspects called the algebra of timed relations. Then we provide offline matching algorithms for TRE and MCL over discrete-valued dense-time behaviors using this framework and study some practical extensions.It is necessary for some application areas such as reactive control that pattern matching needs to be performed during the actual execution of the system. For that, we provide an online matching algorithm for TREs based on the classical technique of derivatives of regular expressions. We believe the underlying technique that combines derivatives and timed relations constitutes another major conceptual contribution for timed systems research.Furthermore, we present an open-source tool Montre that implements our ideas and algorithms. We explore diverse applications of timed pattern matching over several case studies using Montre. Finally we discuss future directions and several open questions emerged as a result of this thesis
9
Berglund, Martin. "Complexities of Order-Related Formal Language Extensions." Doctoral thesis, Umeå universitet, Institutionen för datavetenskap, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-88235.
Full textAbstract:
The work presented in this thesis discusses various formal language formalisms that extend classical formalisms like regular expressions and context-free grammars with additional abilities, most relating to order. This is done while focusing on the impact these extensions have on the efficiency of parsing the languages generated. That is, rather than taking a step up on the Chomsky hierarchy to the context-sensitive languages, which makes parsing very difficult, a smaller step is taken, adding some mechanisms which permit interesting spatial (in)dependencies to be modeled. The most immediate example is shuffle formalisms, where existing language formalisms are extended by introducing operators which generate arbitrary interleavings of argument languages. For example, introducing a shuffle operator to the regular expressions does not make it possible to recognize context-free languages like anbn, but it does capture some non-context-free languages like the language of all strings containing the same number of as, bs and cs. The impact these additions have on parsing has many facets. Other than shuffle operators we also consider formalisms enforcing repeating substrings, formalisms moving substrings around, and formalisms that restrict which substrings may be concatenated. The formalisms studied here all have a number of properties in common. They are closely related to existing regular and context-free formalisms. They operate in a step-wise fashion, deriving strings by sequences of rule applications of individually limited power. Each step generates a constant number of symbols and does not modify parts that have already been generated. That is, strings are built in an additive fashion that does not explode in size (in contrast to e.g. Lindenmayer systems). All languages here will have a semi-linear Parikh image. They feature some interesting characteristic involving order or other spatial constraints. In the example of the shuffle multiple derivations are in a sense interspersed in a way that each is unaware of. All of the formalisms are intended to be limited enough to make an efficient parsing algorithm at least for some cases a reasonable goal. This thesis will give intuitive explanations of a number of formalisms fulfilling these requirements, and will sketch some results relating to the parsing problem for them. This should all be viewed as preparation for the more complete results and explanations featured in the papers given in the appendices.<br>Denna avhandling diskuterar utökningar av klassiska formalismer inom formella språk, till exempel reguljära uttryck och kontextfria grammatiker. Utökningarna handlar på ett eller annat sätt omordning, och ett särskilt fokus ligger på att göra utökningarna på ett sätt som dels har intressanta spatiala/ordningsrelaterade effekter och som dels bevarar den effektiva parsningen som är möjlig för de ursprungliga klassiska formalismerna. Detta står i kontrast till att ta det större steget upp i Chomsky-hierarkin till de kontextkänsliga språken, vilket medför ett svårt parsningsproblem. Ett omedelbart exempel på en sådan utökning är s.k. shuffle-formalismer. Dessa utökar existerande formalismer genom att introducera operatorer som godtyckligt sammanflätar strängar från argumentspråk. Om shuffle-operator introduceras till de reguljära uttrycken ger det inte förmågan att känna igen t.ex. det kontextfria språket anbn, men det fångar istället vissa språk som inte är kontextfria, till exempel språket som består av alla strängar som innehåller lika många a:n, b:n och c:n. Sättet på vilket dessa utökningar påverkar parsningsproblemet är mångfacetterat. Utöver dessa shuffle-operatorer tas också formalismer där delsträngar kan upprepas, formalismer där delsträngar flyttas runt, och formalismer som begränsar hur delsträngar får konkateneras upp. Formalismerna som tas upp här har dock vissa egenskaper gemensamma. De är nära besläktade med de klassiska reguljära och kontextfria formalismerna. De arbetar stegvis, och konstruerar strängar genom successiva applikationer av individuellt enkla regler. Varje steg genererar ett konstant antal symboler och modifierar inte det som redan genererats. Det vill säga, strängar byggs additivt och längden på dem kan inte explodera (i kontrast till t.ex. Lindenmayer-system). Alla språk som tas upp kommer att ha en semi-linjär Parikh-avbildning. De har någon instressant spatial/ordningsrelaterad egenskap. Exempelvis sättet på vilket shuffle-operatorer sammanflätar annars oberoende deriveringar. Alla formalismerna är tänkta att vara begränsade nog att det är resonabelt att ha effektiv parsning som mål. Denna avhandling kommer att ge intuitiva förklaring av ett antal formalismer som uppfyller ovanstående krav, och kommer att skissa en blandning av resultat relaterade till parsningsproblemet för dem. Detta bör ses som förberedande inför läsning av de mer djupgående och komplexa resultaten och förklaringarna i de artiklar som finns inkluderade som appendix.
10
Teichmann, Markus [Verfasser], Heiko [Akademischer Betreuer] [Gutachter] Vogler, and Frank [Gutachter] Drewes. "Expressing Context-Free Tree Languages by Regular Tree Grammars / Markus Teichmann ; Gutachter: Heiko Vogler, Frank Drewes ; Betreuer: Heiko Vogler." Dresden : Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://d-nb.info/1133109616/34.
Full text
11
Brunet, Paul. "Algebras of Relations : from algorithms to formal proofs." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSE1198/document.
Full textAbstract:
Les algèbres de relations apparaissent naturellement dans de nombreux cadres, en informatique comme en mathématiques. Elles constituent en particulier un formalisme tout à fait adapté à la sémantique des programmes impératifs. Les algèbres de Kleene constituent un point de départ : ces algèbres jouissent de résultats de décidabilités très satisfaisants, et admettent une axiomatisation complète. L'objectif de cette thèse a été d'étendre les résultats connus sur les algèbres de Kleene à des extensions de celles-ci.Nous nous sommes tout d'abord intéressés à une extension connue : les algèbres de Kleene avec converse. La décidabilité de ces algèbres était déjà connue, mais l'algorithme prouvant ce résultat était trop compliqué pour être utilisé en pratique. Nous avons donné un algorithme plus simple, plus efficace, et dont la correction est plus facile à établir. Ceci nous a permis de placer ce problème dans la classe de complexité PSpace-complete.Nous avons ensuite étudié les allégories de Kleene. Sur cette extension, peu de résultats étaient connus. En suivant des résultats sur des algèbres proches, nous avons établi l'équivalence du problème d'égalité dans les allégories de Kleene à l'égalité de certains ensembles de graphes. Nous avons ensuite développé un modèle d'automate original (les automates de Petri), basé sur les réseaux de Petri, et avons établi l'équivalence de notre problème original avec le problème de comparaison de ces automates. Nous avons enfin développé un algorithme pour effectuer cette comparaison dans le cadre restreint des treillis de Kleene sans identité. Cet algorithme utilise un espace exponentiel. Néanmoins, nous avons pu établir que la comparaison d'automates de Petri dans ce cas est ExpSpace-complète. Enfin, nous nous sommes intéressés aux algèbres de Kleene Nominales. Nous avons réalisé que les descriptions existantes de ces algèbres n'étaient pas adaptées à la sémantique relationnelle des programmes. Nous les avons donc modifiées pour nos besoins, et ce faisant avons trouvé diverses variations naturelles de ce modèle. Nous avons donc étudié en détails et en Coq les ponts que l'on peut établir entre ces variantes, et entre le modèle “classique” et notre nouvelle version<br>Algebras of relations appear naturally in many contexts, in computer science as well as in mathematics. They constitute a framework well suited to the semantics of imperative programs. Kleene algebra are a starting point: these algebras enjoy very strong decidability properties, and a complete axiomatisation. The goal of this thesis was to export known results from Kleene algebra to some of its extensions. We first considered a known extension: Kleene algebras with converse. Decidability of these algebras was already known, but the algorithm witnessing this result was too complicated to be practical. We proposed a simpler algorithm, more efficient, and whose correctness is easier to establish. It allowed us to prove that this problem lies in the complexity class PSpace-complete.Then we studied Kleene allegories. Few results were known about this extension. Following results about closely related algebras, we established the equivalence between equality in Kleene allegories and equality of certain sets of graphs. We then developed an original automaton model (so-called Petri automata), based on Petri nets. We proved the equivalence between the original problem and comparing these automata. In the restricted setting of identity-free Kleene lattices, we also provided an algorithm performing this comparison. This algorithm uses exponential space. However, we proved that the problem of comparing Petri automata lies in the class ExpSpace-complete.Finally, we studied Nominal Kleene algebras. We realised that existing descriptions of these algebra were not suited to relational semantics of programming languages. We thus modified them accordingly, and doing so uncovered several natural variations of this model. We then studied formally the bridges one could build between these variations, and between the existing model and our new version of it. This study was conducted using the proof assistant Coq
12
Micciancio, Daniele. "The validity problem for extended regular expressions." Thesis, Massachusetts Institute of Technology, 1996. http://hdl.handle.net/1721.1/11046.
Full text
13
Han, Yo-Sub. "Regular languages and codes /." View abstract or full-text, 2005. http://library.ust.hk/cgi/db/thesis.pl?COMP%202005%20HAN.
Full text
14
Fernando, Tim. "Temporal propositions as regular languages." Universität Potsdam, 2008. http://opus.kobv.de/ubp/volltexte/2008/2719/.
Full textAbstract:
Temporal propositions are mapped to sets of strings that witness (in a precise sense) the propositions over discrete linear Kripke frames. The strings are collected into regular languages to ensure the decidability of entailments given by inclusions between languages. (Various notions of bounded entailment are shown to be expressible as language inclusions.) The languages unwind computations implicit in the logical (and temporal) connectives via a system of finite-state constraints adapted from finite-state morphology. Applications to Hybrid Logic and non-monotonic inertial reasoning are briefly considered.
15
Dashkovsky, Boris. "Logical Aspects of Regular Languages." Thesis, McGill University, 1999. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=92139.
Full textAbstract:
A thorough review of selected results on the logical aspects of regular languages includes the theorem of Büchi on monadic second order logic over strings, a characterization of FO[<l and the theorem of 1. Simon. With the help of the Ehrenfeucht-Fraïssé Game we show that :J(k+ltsentences of FO[<1 cannot be expressed as a boolean combination of :J(ktsentences. Block product of finite monoids is used to analyze languages defined by the boolean closure of the 2::2-sentences. Positive varieties and the Mal'cev product are introduced and 2::n +l n IIn+l is shown to be equal to the unambiguous polynomial closure of the nth level of the Straubing-Thérien hierarchy. In particular, 2:: 2 n II2 = VA, where VA is the smallest variety of languages closed under the unambiguous product.<br>Nous proposons un aperçu complet de résultats choisis concernant les aspects logiques des langages réguliers incluant le théorème de Büchi sur la logique monadique de second ordre sur les chaînes de caractères, la caractérisation de FO[<J et le théorème de 1. Simon. Grâce au jeu de Ehrenfeucht-Fraïssé, nous démontrons que, dans FO[<J, les énoncés logiques 3(k+1) ne peuvent être exprimés comme une combinaison booléene d'énoncés 3(k). Nous utilisons le produit bloc de monoïdes finis pour analyser les langages définis par la fermeture booléene des énoncés 2:: 2 • Nous présentons également les variétés positives et le produit de Mal'cev et montrons que 2::n +1 n IIn+1 est égal à la fermeture polynomiale non-ambigue du nième niveau de la hiérarchie de StraubingThérien. En particulier, 2:: 2 n II2 = VA, où VA est la plus petite variété de langages fermée sous le produit non-ambigu fr
16
Juhlin, Cory Michael. "Developing a Compiler for a Regular Expression Based Policy Specification Language." Scholar Commons, 2015. http://scholarcommons.usf.edu/etd/5885.
Full textAbstract:
Security policy specification languages are a response to today's complex and vulnerable software climate. These languages allow an individual or organization to restrict and modify the behavior of third-party applications such that they adhere to the rules specified in the policy. As software grows in complexity, so do the security policies that govern them. Existing policy specification languages have not adapted to the growing complexity of the software they govern and as a result do not scale well, often resulting in code that is overly complex or unreadable. Writing small, isolated policies as separate modules and combining them is known as policy composition, and is an area in which existing policy specification languages have a number of drawbacks. Policy composition is unpredictable and nonstandard with existing languages. PoCo is a new policy specification language that uses signed regular expressions to return sets of allowed and denied actions as output from its policies, allowing policies to be combined with standard set operations in an algebraic way. This thesis covers my contribution to the PoCo project in creating a formal grammar for the language, developing a static analysis tool for policy designers, and implementation of the first PoCo language compiler and runtime for the Java platform.
17
Feng, Yuan. "Improve Data Quality By Using Dependencies And Regular Expressions." Thesis, Mittuniversitetet, Avdelningen för informationssystem och -teknologi, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:miun:diva-35620.
Full textAbstract:
The objective of this study has been to answer the question of finding ways to improve the quality of database. There exists a lot of problems of the data stored in the database, like missing or spelling errors. To deal with the dirty data in the database, this study adopts the conditional functional dependencies and regular expressions to detect and correct data. Based on the former studies of data cleaning methods, this study considers the more complex conditions of database and combines the efficient algorithms to deal with the data. The study shows that by using these methods, the database’s quality can be improved and considering the complexity of time and space, there still has a lot of things to do to make the data cleaning process more efficiency.
18
Weidner, Thomas. "Probabilistic Logic, Probabilistic Regular Expressions, and Constraint Temporal Logic." Doctoral thesis, Universitätsbibliothek Leipzig, 2016. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-208732.
Full textAbstract:
The classic theorems of Büchi and Kleene state the expressive equivalence of finite automata to monadic second order logic and regular expressions, respectively. These fundamental results enjoy applications in nearly every field of theoretical computer science. Around the same time as Büchi and Kleene, Rabin investigated probabilistic finite automata. This equally well established model has applications ranging from natural language processing to probabilistic model checking.
Here, we give probabilistic extensions Büchi\\\'s theorem and Kleene\\\'s theorem to the probabilistic setting. We obtain a probabilistic MSO logic by adding an expected second order quantifier. In the scope of this quantifier, membership is determined by a Bernoulli process. This approach turns out to be universal and is applicable for finite and infinite words as well as for finite trees. In order to prove the expressive equivalence of this probabilistic MSO logic to probabilistic automata, we show a Nivat-theorem, which decomposes a recognisable function into a regular language, homomorphisms, and a probability measure.
For regular expressions, we build upon existing work to obtain probabilistic regular expressions on finite and infinite words. We show the expressive equivalence between these expressions and probabilistic Muller-automata. To handle Muller-acceptance conditions, we give a new construction from probabilistic regular expressions to Muller-automata. Concerning finite trees, we define probabilistic regular tree expressions using a new iteration operator, called infinity-iteration. Again, we show that these expressions are expressively equivalent to probabilistic tree automata.
On a second track of our research we investigate Constraint LTL over multidimensional data words with data values from the infinite tree. Such LTL formulas are evaluated over infinite words, where every position possesses several data values from the infinite tree. Within Constraint LTL on can compare these values from different positions. We show that the model checking problem for this logic is PSPACE-complete via investigating the emptiness problem of Constraint Büchi automata.
19
Mens, Irini-Eleftheria. "Learning regular languages over large alphabets." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM052/document.
Full textAbstract:
L'apprentissage de langages réguliers est un sous-ensemble de l'apprentissage automatique qui s'est révélé utile dans de nombreux domaines tels que l'intelli-gence artificielle, les réseaux de neurones, l'exploration de données, la vérification, etc. De plus, l'intérêt dans les langages définis sur des alphabets infinis ou de grande taille est croissant au fil des années. Même si plusierurs propriétés et théories se généralisent à partir du cas fini, l'apprentissage de tels langages est une tâche difficile.En effet, dans ce contexte, l'application naïve des algorithmes d'apprentissage traditionnel n'est pas possible.Dans cette thèse, nous présentons un schéma algorithmique général pour l'ap-prentissage de langages définis sur des alphabets infinis ou de grande taille, comme par exemple des sous-ensembles bornés de N or R ou des vecteurs booléens de grandes dimensions. Nous nous restreignons aux classes de langages qui sont acceptés par des automates déterministes symboliques utilisant des prédicats pour définir les transitions, construisant ainsi une partition finie de l'alphabet pour chaque état.Notre algorithme d'apprentissage, qui est une adaptation du L* d'Angluin, combine l'apprentissage classique d'un automate par la caractérisation de ses états, avec l'apprentissage de prédicats statiques définissant les partitions de l'alphabet. Nous utilisons l'apprentissage incrémental avec la propriété que deux types de requêtes fournissent une information suffisante sur le langage cible. Les requêtes du premier type sont les requêtes d'adhésions, qui permettent de savoir si un mot proposé appartient ou non au langage cible. Les requêtes du second type sont les requêtes d'équivalence, qui vérifient si un automate proposé accepte le langage cible; dans le cas contraire, un contre-exemple est renvoyé.Nous étudions l'apprentissage de langages définis sur des alphabets infinis ou de grande tailles dans un cadre théorique et général, mais notre objectif est de proposer des solutions concrètes pour un certain nombre de cas particuliers. Ensuite, nous nous intéressons aux deux principaux aspects du problème. Dans un premier temps, nous supposerons que les requêtes d'équivalence renvoient toujours un contre-exemple minimal pour un ordre de longueur-lexicographique quand l'automate proposé est incorrect. Puis dans un second temps, nous relâchons cette hypothèse forte d'un oracle d'équivalence, et nous la remplaçons avec une hypothèse plus réaliste où l'équivalence est approchée par un test sur les requêtes qui utilisent un échantillonnage sur l'ensemble des mots. Dans ce dernier cas, ce type de requêtes ne garantit pas l'obtention de contre-exemples, et par conséquent de contre-exemples minimaux. Nous obtenons alors une notion plus faible d'apprent-issage PAC (Probably Approximately Correct), permettant l'apprentissage d'une approximation du langage cible.Tout les algorithmes ont été implémentés, et leurs performances, en terme de construction d'automate et de taille d'alphabet, ont été évaluées empiriquement<br>Learning regular languages is a branch of machine learning, which has been proved useful in many areas, including artificial intelligence, neural networks, data mining, verification, etc. On the other hand, interest in languages defined over large and infinite alphabets has increased in recent years. Although many theories and properties generalize well from the finite case, learning such languages is not an easy task. As the existing methods for learning regular languages depends on the size of the alphabet, a straightforward generalization in this context is not possible.In this thesis, we present a generic algorithmic scheme that can be used for learning languages defined over large or infinite alphabets, such as bounded subsets of N or R or Boolean vectors of high dimensions. We restrict ourselves to the class of languages accepted by deterministic symbolic automata that use predicates to label transitions, forming a finite partition of the alphabet for every state.Our learning algorithm, an adaptation of Angluin's L*, combines standard automaton learning by state characterization, with the learning of the static predicates that define the alphabet partitions. We use the online learning scheme, where two types of queries provide the necessary information about the target language. The first type, membership queries, answer whether a given word belongs or not to the target. The second, equivalence queries, check whether a conjectured automaton accepts the target language, a counter-example is provided otherwise.We study language learning over large or infinite alphabets within a general framework but our aim is to provide solutions for particular concrete instances. For this, we focus on the two main aspects of the problem. Initially, we assume that equivalence queries always provide a counter-example which is minimal in the length-lexicographic order when the conjecture automaton is incorrect. Then, we drop this ``strong'' equivalence oracle and replace it by a more realistic assumption, where equivalence is approximated by testing queries, which use sampling on the set of words. Such queries are not guaranteed to find counter-examples and certainly not minimal ones. In this case, we obtain the weaker notion of PAC (probably approximately correct) learnability and learn an approximation of the target language. All proposed algorithms have been implemented and their performance, as a function of automaton and alphabet size, has been empirically evaluated
20
Michael, Louis Guy IV. "Exploring the Process and Challenges of Programming with Regular Expressions." Thesis, Virginia Tech, 2019. http://hdl.handle.net/10919/90778.
Full textAbstract:
Regular expressions (regexes) are a powerful mechanism for solving string-matching problems and are supported by all modern programming languages. While regular expressions are highly expressive, they are also often perceived to be highly complex and hard to read. While existing studies have focused on improving the readability of regular expressions, little is known about any other difficulties that developers face when programming with regular expressions. In this paper, we aim to provide a deeper understanding of the process of programming regular expressions by studying: (1) how developers make decisions through the process, (2) what difficulties they face, and (3) how aware they are about serious risks involved in programming regexes. We surveyed 158 professional developers from a diversity of backgrounds, and we conducted a series of interviews to learn more details about the difficulties and solutions that participants face in this process. This mixed methods approach revealed that some of the difficulties of regexes come in the shape of: inability to effectively search for them; fully validate them; and document them. Developers also reported cascading impacts of poor readability, lack of universal portability, and struggling with overall problem comprehension. The majority of our studied developers were unaware of critical security risks that can occur when using regexes, and those that were aware of potential problems felt that they lacked the ability to identify problematic regexes. Our findings provide multiple implications for future work, including development of semantic regex search engines for regex reuse, and improved input generators for regex validation.<br>Master of Science<br>Regular expressions (regexes) are a method to search for a set of matching text. They are easily understood as a way to flexibly search beyond exact matching and are frequently seen in the capacity of the find functionality of ctrl-f. Regexes are also very common in source code for a range of tasks including form validation, where a program needs to confirm that a user provided information that conformed to a specific structure, such as an email address. Despite being a widely supported programming feature, little is known about how developers go about creating regexes or what they struggle with when doing so. To gain a better understanding of how regexes are created and reused, we surveyed 158 professional developers from a diversity of backgrounds and experience levels about their processes and perceptions about regexes. As a followup to the survey we conducted a series of interviews focusing on the challenges faced by developers when tackling problems for which they felt that a regex was worth using. Through the combination of these studies, we developed a detailed understanding of how professional developers create regexes as well as many of the struggles that they face when doing so. These challenges come in the form of the inability to effectively search for, fully validate, and document regexes, as well as the cascading impacts of poor readability, lack of universal portability, and overall problem comprehension.
21
Ada, Anil. "Non-deterministic communication complexity of regular languages." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=112367.
Full textAbstract:
The notion of communication complexity was introduced by Yao in his seminal paper [Yao79]. In [BFS86], Babai Frankl and Simon developed a rich structure of communication complexity classes to understand the relationships between various models of communication complexity. This made it apparent that communication complexity was a self-contained mini-world within complexity theory. In this thesis, we study the place of regular languages within this mini-world. In particular, we are interested in the non-deterministic communication complexity of regular languages.<br>We show that a regular language has either O(1) or O(log n) non-deterministic complexity. We obtain several linear lower bound results which cover a wide range of regular languages having linear non-deterministic complexity. These lower bound results also imply a result in semigroup theory: we obtain sufficient conditions for not being in the positive variety Pol(Com).<br>To obtain our results, we use algebraic techniques. In the study of regular languages, the algebraic point of view pioneered by Eilenberg ([Eil74]) has led to many interesting results. Viewing a semigroup as a computational device that recognizes languages has proven to be prolific from both semigroup theory and formal languages perspectives. In this thesis, we provide further instances of such mutualism.
22
Martin, Torres Gabriela Susana. "Rough approximations in varieties of regular languages." Doctoral thesis, Universitat Rovira i Virgili, 2016. http://hdl.handle.net/10803/379823.
Full textAbstract:
En aquest treball s'estudien aproximacions de llenguatges regulars per membres d'una varietat de llenguatges regulars donada. Es tracta d'aproximacions superiors o inferiors en el sentit de la teoria dels conjunts aproximats (Rough set theory) de Pawlak. Les relacions utilitzades per a les aproximacions són les congruències corresponents a la varietat de llenguatges regulars considerada. En particular, s'estudia l'existència de les aproximacions superior mínima i inferior màxima. En les anomenades varietats principals, aquestes sempre existeixen, i presentem algorismes per trobar-les.
Per a varietats no principals, la situació és molt més complexa. En aquest cas estudiem les condicions per a la seva existència. Concretament, considerem varietats que són unió d'una família dirigida de varietats principals, i també varietats pseudo-principals, que es defineixen en aquest treball.
A continuació estudiem la precisió de les aproximacions, utilitzant la densitat relativa entre el llenguatge objecte i la seva aproximació, observant després el seu comportament asimptòtic. Aquesta mesura de la precisió és aplicada a les aproximacions en les famílies de llenguatges k-definits, k-definits inversos, i,j-definits, k-testables i commutatius.
Finalment examinem aproximacions sota relacions de indiscernibilitat, l'índex de les quals és infinit, seguint el treball de Paun, Polkowsky i Skowron (1997), i analitzem fins a quin punt poden ser estudiades dins del nostre marc teòric. Descrivim algunes de les seves característiques generals, comparant-les amb algunes de les famílies ja presentades, i en alguns casos, introduïm modificacions en les seves definicions per obtenir relacions de congruència.
Encara que en aquesta tesi considerem sobretot varietats d’Eilenberg, les idees poden ser aplicades a altres tipus de varietats de llenguatges. El nostre treball també pot ser considerat com un abordatge al problema<br>En este trabajo se estudian aproximaciones de lenguajes regulares por miembros de una variedad de lenguajes regulares dada. Se trata de aproximaciones superiores o inferiores en el sentido de la teoría de los conjuntos approximados (Rough set theory) de Pawlak. Las relaciones utilizadas para las aproximaciones son las congruencias correspondientes a la variedad de lenguages regulares considerada. En particular, se estudia la existencia de las aproximaciones superior mínima e inferior máxima. En las llamadas variedades principales, éstas siempre existen, y presentamos algoritmos para hallarlas.
Para variedades no principales, la situación es mucho más compleja. En este caso estudiamos las condiciones para su existencia. Concretamente, consideramos variedades que son unión de una familia dirigida de variedades principales, y también variedades pseudo-principales, que se definen en este trabajo.
A continuación estudiamos la precisión de las aproximaciones, utilizando la densidad relativa entre el lenguaje objeto y su aproximación, observando luego su comportamiento asintótico. Esta medida de la precisión es aplicada a las aproximaciones en las familias de lenguajes k-definidos, k-definidos inversos, i,j-definidos, k-testables y conmutativos.
Finalmente examinamos aproximaciones bajo relaciones de indiscernibilidad, cuyo índice es infinito, siguiendo el trabajo de Paun, Polkowsky y Skowron (1997), y analizamos hasta qué punto pueden ser estudiadas dentro de nuestro marco teórico. Describimos algunas de sus características generales, comparándolas con algunas de las familias ya presentadas, y en algunos casos, introducimos modificaciones en sus definiciones para obtener relaciones de congruencia.
Aunque en esta tesis consideramos sobre todo variedades de Eilenberg, las ideas pueden ser aplicadas a otros tipos de variedades de lenguajes. Nuestro trabajo también puede ser considerado como un abordaje al problema de la inferencia caracterizable, en la cual a partir de una muestra, se infiere un lenguaje de un tipo determinado.<br>We study approximations of regular languages by members of a given variety of regular languages. These are upper or lower approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to the given variety of regular languages. In particular, we consider the closest upper and lower approximations in the later. In the so-called principal varieties these always exist, and we present
algorithms for finding them, but for other varieties the situation is more complex.
For non-principal +-varieties we study conditions for the existence of the closest upper and lower approximations. In particular, we consider varieties that are the union of a directed family of principal +-varieties, and pseudo-principal +-varieties, that are defined in this work.
Next, we consider the accuracy of the considered approximations, measured by the relative density of the object language in the approximation language and the asymptotic behavior of this quotient. In particular, we apply our measures of accuracy to k-definite, reverse k-definite, i,j-definite, k-testable and commutative approximations.
Finally, we examine rough approximations under some infinite index indiscernibility relations as they were presented by Paun, Polkowski and Skowron (1997), looking at how they fit in our framework. We study their general features, comparing them with some of the families already studied, and in some cases introducing modifications in
their definitions to make them congruences.
Although we consider mostly Eilenberg’s +-varieties, the general ideas apply also to other types of varieties of languages. Our work may also be viewed as an approach to the characterizable inference problem in which a language of a certain kind is to be inferred from a given sample.
23
Cogliati, Joshua Joseph. "Visualizing the pumping lemma for regular languages." Thesis, Montana State University, 2004. http://etd.lib.montana.edu/etd/2004/cogliati/CogliatiJ0805.pdf.
Full text
24
Helmersson, Benjamin. "Definition Extraction From Swedish Technical Documentation : Bridging the gap between industry and academy approaches." Thesis, Linköpings universitet, Institutionen för datavetenskap, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-131057.
Full textAbstract:
Terminology is concerned with the creation and maintenance of concept systems, terms and definitions. Automatic term and definition extraction is used to simplify this otherwise manual and sometimes tedious process. This thesis presents an integrated approach of pattern matching and machine learning, utilising feature vectors in which each feature is a Boolean function of a regular expression. The integrated approach is compared with the two more classic approaches, showing a significant increase in recall while maintaining a comparable precision score. Less promising is the negative correlation between the performance of the integrated approach and training size. Further research is suggested.
25
Delaney, Aidan. "Defining star-free regular languages using diagrammatic logic." Thesis, University of Brighton, 2012. https://research.brighton.ac.uk/en/studentTheses/d1c53bda-f520-4807-9de9-8de12eda3d9e.
Full textAbstract:
Spider diagrams are a recently developed visual logic that make statements about relationships between sets, their members and their cardinalities. By contrast, the study of regular languages is one of the oldest active branches of computer science research. The work in this thesis examines the previously unstudied relationship between spider diagrams and regular languages. In this thesis, the existing spider diagram logic and the underlying semantic theory is extended to allow direct comparison of spider diagrams and star-free regular languages. Thus it is established that each spider diagram defines a commutative star-free regular language. Moreover, we establish that every com- mutative star-free regular language is definable by a spider diagram. From the study of relationships between spider diagrams and commutative star-free regular languages, an extension of spider diagrams is provided. This logic, called spider diagrams of order, increases the expressiveness of spider di- agrams such that the language of every spider diagram of order is star-free and regular, but not-necessarily commutative. Further results concerning the expres- sive power of spider diagrams of order are gained through the use of a normal form for the diagrams. Sound reasoning rules which take a spider diagram of order and produce a semantically equivalent diagram in the normal form are pro- vided. A proof that spider diagrams of order define precisely the star-free regular languages is subsequently presented. Further insight into the structure and use of spider diagrams of order is demonstrated by restricting the syntax of the logic. Specifically, we remove spiders from spider diagrams of order. We compare the expressiveness of this restricted fragment of spider diagrams of order with the unrestricted logic.
26
Volden, Kjetil. "Compiling Regular Expressions into Non-Deterministic State Machines for Simulation in SystemC." Thesis, Norges teknisk-naturvitenskapelige universitet, Institutt for elektronikk og telekommunikasjon, 2011. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-15083.
Full textAbstract:
With Moore’s law exponentially increasing the number of transistors on inte-grated circuits, developers fail to keep up. This makes chip area an increasinglycheap resource. At the same time, researchers and developers are trying to findways to dynamically reconfigure FPGAs, preferably at run time, so as to in-crease the flexibility of hardware solutions, and close the gap between the speedof hardware and flexibility of software. A proposed way of solving both of theseissues at once is by using nondeterministic finite-state machines as a fundamen-tal unit of design. This could provide great flexibility and dynamic hardwaresolutions, but before this can be known for sure, a system like this would needto be simulated. This paper documents the planning and development of a Sys-temC library that creates nondeterministic finite-state machines from regularexpressions, and a special regular expression syntax designed for this specificapplication. The paper can also be used as a reference for the inner workingsof, and how to use, the library.
27
Gruber, Hermann. "On the descriptional and algorithmic complexity of regular languages." Lichtenberg (Odw.) Harland Media, 2009. http://d-nb.info/998400602/04.
Full text
28
Duvenage, Eugene. "miRNAMatcher: High throughput miRNA discovery using regular expressions obtained via a genetic algorithm." Thesis, University of the Western Cape, 2008. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_5752_1266536340.
Full textAbstract:
<p>In summary there currently exist techniques to discover miRNA however both require many calculations to be performed during the identification limiting their use at a genomic level. Machine learning techniques are currently providing the best results by combining a number of calculated and statistically derived features to identify miRNA candidates, however almost all of these still include computationally intensive secondary-structure calculations. It is the aim of this project to produce a miRNA identification process that minimises and simplifies the number of computational elements required during the identification process.</p>
29
Khan, Tafseer Ahmed [Verfasser]. "Spatial Expressions and Case in South Asian Languages / Tafseer Ahmed Khan." Konstanz : Bibliothek der Universität Konstanz, 2009. http://d-nb.info/1017235945/34.
Full text
30
Wagner, Mitchell James. "Reconstructing Signaling Pathways Using Regular-Language Constrained Paths." Thesis, Virginia Tech, 2018. http://hdl.handle.net/10919/85044.
Full textAbstract:
Signaling pathways are widely studied in systems biology. Several databases catalog our knowledge of these pathways, including the proteins and interactions that comprise them. However, high-quality curation of this information is slow and painstaking. As a result, many interactions still lack annotation concerning the pathways they participate in. A natural question that arises is whether or not it is possible to automatically leverage existing annotations to identify new interactions for inclusion in a given pathway.
Here, we present RegLinker, an algorithm that achieves this purpose by computing multiple short paths from pathway receptors to transcription factors (TFs) within a background interaction network. The key idea underlying RegLinker is the use of regular-language constraints to control the number of non-pathway edges present in the computed paths. We systematically evaluate RegLinker and alternative approaches against a comprehensive set of 15 signaling pathways and demonstrate that RegLinker exhibits superior recovery of withheld pathway proteins and interactions. These results show the promise of our approach for prioritizing candidates for experimental study and the broader potential of automated analysis to attenuate difficulties of traditional manual inquiry.<br>Master of Science
31
Olschewski, Jörg [Verfasser]. "Languages and strategies : a study of regular infinite games / Jörg Olschewski." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2014. http://d-nb.info/104956121X/34.
Full text
32
Haudebourg, Timothée. "Automatic verification of higher-order functional programs using regular tree languages." Thesis, Rennes 1, 2020. http://www.theses.fr/2020REN1S060.
Full textAbstract:
Nous étudions comment les langages réguliers d'arbres peuvent être utilisés pour vérifier automatiquement des propriétés sur des programmes fonctionnels d'ordre supérieur. Notre but est de développer de nouvelles techniques et outils pour les programmeurs permettant de développer des programmes plus sûrs tout en réduisant le temps et l'expertise nécessaire pour les vérifier. Cette thèse se concentre sur la vérification de propriétés régulières, famille pour laquelle nous montrons qu'une vérification complète et automatique est possible. Notre méthode de vérification est construite sur une procédure d'abstraction capable d'apprendre des langages réguliers sur-approchant les états atteignables d'un programme. En utilisant les langages réguliers en tant que types, nous montrons comment modulariser cette procédure pour vérifier des propriétés complexes en les formulant en tant que problèmes d'inférence des types. Nous étudions ses performances au travers de notre implémentation OCaml, Timbuk4, sur plus de 80 problèmes de vérification. Nous montrons ensuite que notre procédure d'abstraction peut être utilisée pour vérifier des propriété relationnelles qui semblaient hors de portée des langages réguliers. Pour cela, nous utilisons et étendons un opérateur de convolution sur les arbres pour représenter une relation par langage régulier. Nous étendons ensuite notre procédure d'apprentissage de langages pour inférer automatiquement ces relations. Nous proposons une implémentation de cette idée en Rust en tant solveur de systèmes de clauses de Horn contraintes et étudions ses performances sur de multiples problèmes relationnels<br>This thesis studies how regular tree languages can be used to automatically verify properties on higher-order functional programs. Our goal is to develop new techniques and tools for the programmers to develop safer programs while reducing the time and expertise needed to verify them. In particular, we focus on the automatic verification of regular safety properties, a family of properties for which we show that completely and fully automatic verification can be achieved. Our verification method is build upon a regular abstraction procedure that can automatically learn regular tree languages that over-approximates of the reachable states of a program, allowing the verification of a target property. By using regular languages as types we modularize this procedure to verify complex properties by stating them as type inference problems. In addition we study the performances of the overall technique in our prototype OCaml implementation in the Timbuk4 verification framework over a test suite of more than 80 verification problems. We then show how our abstraction procedure can be used to verify relational properties that seemed out of the scope of regular tree languages. To do that, we use and extend a convolution operator on trees to represent every element of a relation into a regular tree language. We can then extend our previously defied regular language learning procedure to automatically infer such regular relations. We propose a Rust implementation of this idea as a regular solver for Constrained Horn Clauses systems and study its performance on several relational verification problems
33
Hoffmann, Ruth. "On dots in boxes, or permutation pattern classes and regular languages." Thesis, University of St Andrews, 2015. http://hdl.handle.net/10023/7034.
Full textAbstract:
This thesis investigates permutation pattern classes in a language theoretic context. Specifically we explored the regularity of sets of permutations under the rank encoding. We found that the subsets of plus- and minus-(in)decomposable permutations of a regular pattern class under the rank encoding are also regular languages under that encoding. Further we investigated the sets of permutations, which in their block-decomposition have the same simple permutation, and again we found that these sets of permutations are regular languages under the rank encoding. This natural progression from plus- and minus-decomposable to simple decomposable permutations led us further to the set of simple permutations under the rank encoding, which we have also shown to be regular under the rank encoding. This regular language enables us to find the set of simple permutations of any class, independent of whether the class is regular under the rank encoding. Furthermore the regularity of the languages of some types of classes is discussed. Under the rank encoding we show that in general the skew-sum of classes, separable classes and wreath classes are not regular languages; but that the direct-sum of classes, and with some restrictions on the cardinality of the input classes the skew-sum and wreath sum of classes in fact are regular under this encoding. Other encodings such as the insertion encoding and the geometric grid encoding are discussed and in the case of the geometric grid encoding alternative and constructive ways of retrieving the basis of a geometric grid class are suggested. The aforementioned results of the rank encoding have been implemented, amongst other previously shown results, and tested. The program is available and accessible to everyone. We show that the implementation for finding the block-decomposition of a permutation has cubic time complexity with respect to the length of the permutation. The code for constructing the automaton that accepts the language of all plus-indecomposable permutations of a regular class under the rank encoding has quadratic time complexity with respect to the alphabet of the language. The procedure to find the automaton that accepts the language of minus-decomposable permutations has complexity O(k⁵) and we show that the implementation of the automaton to find the language of simple permutations under the rank encoding has time complexity O(k⁵ 2ᵏ), where k is the size of the alphabet. Further we show benchmark testing on previous important results involving the rank encoding on classes and their bases.
34
Tew, Kevin. "Skuery : manipulation of S-expressions using Xquery techniques /." Diss., CLICK HERE for online access, 2006. http://contentdm.lib.byu.edu/ETD/image/etd1677.pdf.
Full text
35
Davis, James Collins. "On the Impact and Defeat of Regular Expression Denial of Service." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/98593.
Full textAbstract:
Regular expressions (regexes) are a widely-used yet little-studied software component. Engineers use regexes to match domain-specific languages of strings. Unfortunately, many regex engine implementations perform these matches with worst-case polynomial or exponential time complexity in the length of the string. Because they are commonly used in user-facing contexts, super-linear regexes are a potential denial of service vector known as Regular expression Denial of Service (ReDoS). Part I gives the necessary background to understand this problem.
In Part II of this dissertation, I present the first large-scale empirical studies of super-linear regex use. Guided by case studies of ReDoS issues in practice (Chapter 3), I report that the risk of ReDoS affects up to 10% of the regexes used in practice (Chapter 4), and that these findings generalize to software written in eight popular programming languages (Chapter 5). ReDoS appears to be a widespread vulnerability, motivating the consideration of defenses.
In Part III I present the first systematic comparison of ReDoS defenses. Based on the necessary conditions for ReDoS, a ReDoS defense can be erected at the application level, the regex engine level, or the framework/runtime level. In my experiments I report that application-level defenses are difficult and error prone to implement (Chapter 6), that finding a compatible higher-performing regex engine is unlikely (Chapter 7), that optimizing an existing regex engine using memoization incurs (perhaps acceptable) space overheads (Chapter 8), and that incorporating resource caps into the framework or runtime is feasible but faces barriers to adoption (Chapter 9).
In Part IV of this dissertation, we reflect on our findings. By leveraging empirical software engineering techniques, we have exposed the scope of potential ReDoS vulnerabilities, and given strong motivation for a solution. To assist practitioners, we have conducted a systematic evaluation of the solution space. We hope that our findings assist in the elimination of ReDoS, and more generally that we have provided a case study in the value of data-driven software engineering.<br>Doctor of Philosophy<br>Software commonly performs pattern-matching tasks on strings. For example, when validating input in a Web form, software commonly tests whether an input fits the pattern of a credit card number or an email address. Software engineers often implement such string-based pattern matching using a tool called regular expressions (regexes). Regexes permit software engineers to succinctly describe the sequences of characters that make up common "languages" like the set of valid Visa credit card numbers (16 digits, starting with a 4) or the set of valid emails (some characters, an '@', and more characters including at least one'.'). Using regexes on untrusted user input in this manner may be a dangerous decision because some regexes take a long time to evaluate. These slow regexes can be exploited by attackers in order to carry out a denial of service attack known as Regular expression Denial of Service (ReDoS). To date, ReDoS has led to outages affecting hundreds of websites and tens of thousands of users.
While the risk of ReDoS is well known in theory, in this dissertation I present the first large-scale empirical studies measuring the extent to which slow regular expressions are used in practice. I found that about 10% of real regular expressions extracted from hundreds of thousands of software projects can exhibit longer-than-expected worst-case behavior in popular programming languages including JavaScript, Python, and Ruby. Motivated by these findings, I then consider a range of ReDoS solution approaches: application refactoring, regex engine replacement, regex engine optimization, and resource caps. I report that application refactoring is error-prone, and that regex engine replacement seems unlikely due to incompatibilities between regex engines. Some resource caps are more successful than others, but all resource cap approaches struggle with adoption. My novel regex engine optimizations seem the most promising approach for protecting existing regex engines, offering significant time reductions with acceptable space overheads.
36
Wang, Zhen. "Static type analysis of XQuery expressions using rewriting calculus." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/hkuto/record/B38882966.
Full text
37
Wang, Zhen, and 王珍. "Static type analysis of XQuery expressions using rewriting calculus." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B38882966.
Full text
38
Gulan, Stefan [Verfasser], and Henning [Akademischer Betreuer] Fernau. "On the Relative Descriptional Complexity of Regular Expressions and Finite Automata / Stefan Gulan ; Betreuer: Henning Fernau." Trier : Universität Trier, 2012. http://d-nb.info/1197697942/34.
Full text
39
Raitt, Lesley Anne. "Random generation of finite automata over the domain of the regular languages." Thesis, Stellenbosch : Stellenbosch University, 2006. http://hdl.handle.net/10019.1/19646.
Full textAbstract:
Thesis (MSc)--University of Stellenbosch, 2007.<br>ENGLISH ABSTRACT: The random generation of finite automata over the domain of their graph structures is a wellknown
problem. However, random generation of finite automata over the domain of the regular
languages has not been studied in such detail. Random generation algorithms designed for this
domain would be useful for the investigation of the properties of the regular languages associated
with the finite automata.
We studied the existing enumerations and algorithms to randomly generate UDFAs and binary
DFAs as they pertained to the domain of the regular languages. We evaluated the algorithms
experimentally across the domain of the regular languages for small values of n and found the distributions
non-uniform. Therefore, for UDFAs, we derived an algorithm for the random generation
of UDFAs over the domain of the regular languages from Domaratzki et. al.’s [9] enumeration of
the domain of the regular languages. Furthermore, for binary DFAs, we concluded that for large
values of n, the bijection method is a viable means of randomly generating binary DFAs over the
domain of the regular langagues.
We looked at all the random generation of union-UNFAs and -UNFAs across the domain of
the regular languages. Our study of these UNFAs took all possible variables for the generation of
UNFAs into account. The random generation of UNFAs over the domain of the regular languages
is an open problem<br>AFRIKAANSE OPSOMMING: Die ewekansige generasie van eindige toestand outomate (eto’s) oor die domein van hul grafiekstrukture
is ’n bekende probleem. Nieteenstaande het die ewekansige generasie van eindige toestand
outomate oor die domein van die regulˆere tale nie soveel aandag gekry nie. Algoritmes wat eindige
toestand outomate ewekansig genereer oor die domein van die regulˆere tale sal nuttig wees om die
ondersoek van die eienskappe van regulˆere tale, wat met eto’s verbind is, te bewerkstellig.
Ons het die bestaande aftellings en algoritmes bestudeer vir die ewekansige generasie van deterministiese
eindige toestand outomate (deto’s) met een en twee alfabetiese simbole soos dit betrekking
het op die domein van die regulˆere tale bestudeer. Ons het die algoritmes eksperimenteel beoordeel
oor die domein van die regulˆere tale vir outomate met min toestande en bevind dat die
verspreiding nie eenvomig is nie. Daarom het ons ’n algoritme afgelei vir die ewekansige generasie
van deto’s met een alfabetsimbool oor die domein van die regulˆere tale van Domaratzki et. al. [9]
se aftelling. Bowendien, in die geval van deto’s met twee alfabetsimbole met ’n groot hoeveelheid
toestande is die ‘bijeksie metode ’n goeie algoritme om te gebruik vir die ewekansige generasie van
hierdie deto’s oor die domein van die regulˆere tale.
Ons het ook die ewekansige generasie van [-nie-deterministiese eindige toestand outomate en
-nie-deterministiese eindige toestand outomate oor die domein van die regulˆere tale bestudeer.
Ons studie van hierdie neto’s het alle moontlike veranderlikes in ageneem. Die ewekansige generering
van deto’s oor die domein van die regulˆere tale is ’n ope probleem.
40
Rahm, Ludwig. "Generating functions and regular languages of walks with modular restrictions in graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-138117.
Full textAbstract:
This thesis examines the problem of counting and describing walks in graphs, and the problem when such walks have modular restrictions on how many timesit visits each vertex. For the special cases of the path graph, the cycle graph, the grid graph and the cylinder graph, generating functions and regular languages for their walks and walks with modular restrictions are constructed. At the end of the thesis, a theorem is proved that connects the generating function for walks in a graph to the generating function for walks in a covering graph.
41
Al-Taher, M. A. "The translation of intertextual expressions in political articles." Thesis, University of Salford, 2008. http://usir.salford.ac.uk/2196/.
Full textAbstract:
The study discusses the translation of intertextual expressions in political articles, aiming at understanding the role of intertextuality within the cultural, ideological and individual circles. Critical discourse analysis shows clearly how indispensible intertextuality is to political discourse in particular as a major ideological tool, especially in the information age when the media employ numerous forms of intertextuality to reinforce their message in terms of legitimisation or delegitimisation. Political newspaper comments tend to belong to the argumentative or vocative (appellative) type of texts, which are intended to achieve a maximum impact on the receiver. In an attempt to relay intertextual expressions across languages, a culture-specific problem is mainly found since different aspects of intertextuality are likely to arise in social, historical, religious and literary terrns which form the unique background of each culture. It is suggested that a three-stage process underpins the successful translation of intertextual expressions. First, an intertextual expression needs to be identified; second, its 'host of associations' have to be fully comprehended; thirdly, the appropriate type of equivalence is to be chosen to 'reflect the same ideological force' of the original expression. This is often achieved by means of functional equivalencc, which provides corresponding target language culture expressions that are expected to 'Invoke the same effect' of those of the source language culture.
42
Kayyal, Mary Hanna. "Judgments of Spontaneous Facial Expressions of Emotion across Cultures and Languages: Testing the Universality Thesis." Thesis, Boston College, 2014. http://hdl.handle.net/2345/bc-ir:104355.
Full textAbstract:
Thesis advisor: James A. Russell<br>The claim that certain emotions are universally recognized from facial expressions is based primarily on the study of expressions that were posed. The current study was of spontaneous facial expressions shown by aborigines in Papua New Guinea (Ekman, 1980) -- 18 faces claimed to convey one (or, in the case of blends, two) basic emotions and four faces claimed to show other universal feelings. For each face, ten samples of observers-- South Koreans speaking Korean (n=66), Spaniards speaking Spanish (n=54), Israelis speaking Hebrew (n=60), Chinese speaking English (n=83), Chinese speaking Cantonese (n=64), Japanese speaking English (n=71), Japanese speaking Japanese (n=72), Indians speaking English (n=65), Indians speaking Kannada (n=62), and Indians speaking Hindi (n=120)--rated the degree to which each of the 12 predicted emotions or feelings was conveyed. The modal choice across all ten samples of observers was the predicted label for only 2 (of the 22) faces, predicted to convey exclusively happiness. Observers endorsed the predicted emotion or feeling moderately often (mean=56%), but also denied it moderately often (mean=44%). They also endorsed more than one (or, for blends, two) label(s) in each face - on average, 1.8 of basic emotions and 3.7 of other feelings. There were both similarities and differences across culture and language, but the emotional meaning of a facial expression is not well captured by the predicted label(s) or, indeed, by any single label<br>Thesis (PhD) — Boston College, 2014<br>Submitted to: Boston College. Graduate School of Arts and Sciences<br>Discipline: Psychology
43
Ndlovu, Sambulo. "A comparative analysis of metaphorical expressions used by rural and urban Ndebele speakers: the contribution of S'ncamtho." Doctoral thesis, University of Cape Town, 2018. http://hdl.handle.net/11427/29515.
Full textAbstract:
This thesis explores language expansion and change through metaphorical expressions that originate with urban youth varieties. It focuses on the impact of S'ncamtho, an Ndebele-based urban youth variety of Bulawayo in Zimbabwe along the variables of rural/urban, sex, age and level of education. The thesis uses Cognitive Metaphor Theory to build on research on metaphor in urban youth varieties to answer the overarching question; how is S'ncamtho impacting Ndebele? It confirms that sex and sexuality, music and partying, love and relationships are popular themes in S'ncamtho. The thesis identifies relexicalisation and replacement of metaphoric vehicles as the main metaphor derivational strategies in S'ncamtho and confirms the existence of clearly discernible genres of metaphor in S'ncamtho which are proverbs, sayings, aphorisms and euphemistic metaphors. While S'ncamtho and other youth varieties in Africa have been identified as urban varieties, the study brings in the dimension of measuring the spread of S'ncamtho to peri-urban and rural areas. Data from questionnaire tests, interviews and observations is analysed using the Idiom Familiarity and Comprehension Judgement Method to measure the impact and spread of S'ncamtho metaphors. The guiding theory in evaluating the spread of S'ncamtho metaphors is a Social Psychology framework- Social Impact Theory (SIT). The thesis argues that S'ncamtho metaphors spread outside Bulawayo’s high density male youth to female and older Ndebele speakers in and outside the city, it identifies male youth in the age cohort 15- 35 years as more familiar and using more S'ncamtho metaphors compared to females and older males in urban, peri-urban and rural areas. It also reveals that S'ncamtho metaphor familiarity declines with age and distance from Bulawayo, and that generally females use less S'ncamtho compared to males and the young are more familiar with S'ncamtho compared to adults. The research reveals that there is no significant difference between rural and urban professionals in S'ncamtho metaphor familiarity and this confirms that improved communication networks impact on the spread of S'ncamtho as professional people frequent Bulawayo for pay and other services. However, the study also noted that there are still more people who have negative attitudes towards S'ncamtho, compared to those who view its impact positively. The thesis argues that the popularity of S'ncamtho has seen S'ncamtho metaphors operating in professions including journalism, health professions, teaching and religious professions. Furthermore, attitudes are changing as some people have begun to view S'ncamtho positively outside the criminal prejudices.
44
Fangfang, Wang. "The Metaphorical and Metonymical Expressions including Face and Eye in Everyday Language." Thesis, Högskolan Kristianstad, Enheten för lärarutbildning, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:hkr:diva-5900.
Full text
45
Cooper, Andrew. "Regular Word Order in The Wanderer." Thesis, Stockholms universitet, Engelska institutionen, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-64070.
Full textAbstract:
Background: Grammars of Old English held at least until the 1960s that word orderin Anglo-Saxon texts was essentially “free”, that is, determined entirely or primarily by stylistic choice rather than syntactic rules. Although prose word order has been shown to be regular in several models, the same cannot be said of poetry. This study uses Nils-Lennart Johannesson’s Old English syntax model, operating within the Government and Binding framework, to establish whether the phrase structure of The Wanderer can fit into this model as it stands, and if not, whether a reasonably small number of additional parameters can be established in order to establish whether “free” word order is in evidence, or whether the word order of Old English poetry is regular in the same way as prose. Results: A full clause analysis showed that the majority of the clauses fit Johannesson’s model. For those which did not, two modifications are recommended: non-compulsory movement of main verbs in main clauses from I to C; and the splitting and rightwards extraposition of the second part of coordinated NPs in which the first coordinated element is “light” and the second “heavy”. This leaves a small number of clauses featuring constructions which do not occur frequently enough in the text to allow rules to be induced to explain them. These must therefore be deemed irregular. Conclusions: While much of The Wanderer has been shown to be syntactically regular, some constructions could not be fitted into the existing model without the introduction of special parameters to excuse them. This paper is intended as a pilot study for a larger project which will incorporate the other poems in the heroic tradition with the hope of inducing a complete syntax for them. One part of that investigation will be to include these infrequent constructions in The Wanderer, to find comparable constructions in other poems and categorise them within the corpus.
46
Losemann, Katja [Verfasser], and Wim [Akademischer Betreuer] Martens. "Foundations of Regular Languages for Processing RDF and XML / Katja Losemann. Betreuer: Wim Martens." Bayreuth : Universität Bayreuth, 2015. http://d-nb.info/1079588620/34.
Full text
47
Kühnberger, Kai-Uwe. "Formal frameworks for circular phenomena possibilities of modeling pathological expressions in formal and natural languages /." [S.l. : s.n.], 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=964198576.
Full text
48
Krawetz, Bryan. "Monoids and the State Complexity of the Operation root(L)." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1034.
Full textAbstract:
In this thesis, we cover the general topic of state complexity. In particular, we examine the bounds on the state complexity of some different representations of regular languages. As well, we consider the state complexity of the operation root(<i>L</i>).
We give quick treatment of the deterministic state complexity bounds for nondeterministic finite automata and regular expressions. This includes an improvement on the worst-case lower bound for a regular expression, relative to its alphabetic length.
The focus of this thesis is the study of the increase in state complexity of a regular language <i>L</i> under the operation root(<i>L</i>). This operation requires us to examine the connections between abstract algebra and formal languages.
We present results, some original to this thesis, concerning the size of the largest monoid generated by two elements. Also, we give good bounds on the worst-case state complexity of root(<i>L</i>). In turn, these new results concerning root(<i>L</i>) allow us to improve previous bounds given for the state complexity of two-way deterministic finite automata.
49
Strauss, Marthinus David. "Process-based decomposition and multicore performance : case studies from Stringology." Thesis, University of Pretoria, 2017. http://hdl.handle.net/2263/61273.
Full textAbstract:
Current computing hardware supports parallelism at various levels. Conventional programming techniques, however, do not utilise efficiently this growing resource. This thesis seeks a better fit between software and current hardware while following a hardware-agnostic software development approach. This allows the programmer to remain focussed on the problem domain. The thesis proposes process-based problem decomposition as a natural way to structure a concurrent implementation that may also improve multicore utilisation and, consequently, run-time performance.
The thesis presents four algorithms as case studies from the domain of string pattern matching and finite automata.
Each case study is conducted in the following manner. The particular sequential algorithm is decomposed into a number of communicating concurrent processes. This decomposition is described in the process algebra CSP. Hoare's CSP was chosen as one of the best known process algebras, for its expressive power, conciseness, and overall simplicity.
Once the CSP-based process description has brought ideas to a certain level of maturity, the description is translated into a process-based implementation. The Go programming language was used for the implementation as its concurrency features were inspired by CSP. The performance of the process-based implementation is then compared against its conventional sequential version (also provided in Go).
The goal is not to achieve maximal performance, but to compare the run-time performance of an ``ordinary'' programming effort that focussed on a process-based solution over a conventional sequential implementation.
Although some implementations did not perform as well as others, some did significantly outperform their sequential counterparts. The thesis thus provides prima facie evidence that a process-based decomposition approach is promising for achieving a better fit between software and current multicore hardware.<br>Thesis (PhD)--University of Pretoria, 2017.<br>Computer Science<br>PhD<br>Unrestricted
50
Weidner, Thomas [Verfasser], Manfred [Akademischer Betreuer] Droste, Manfred [Gutachter] Droste, and Benedikt [Gutachter] Bollig. "Probabilistic Logic, Probabilistic Regular Expressions, and Constraint Temporal Logic / Thomas Weidner ; Gutachter: Manfred Droste, Benedikt Bollig ; Betreuer: Manfred Droste." Leipzig : Universitätsbibliothek Leipzig, 2016. http://d-nb.info/1240627777/34.
Full text