Scientific Applications of Language Methods

The following sections are included:

• Preface

• Contents

The purpose of the paper is to give an introductory survey of the main aspects and results regarding the relative succinctness of different representations of languages, such as finite automata, regular expressions, push-down automata and variants thereof, context-free grammars, and descriptional systems from a more abstract perspective. Basic properties of these descriptional systems and their size measures are addressed. The trade-offs between different representations are either bounded by some recursive function, or reveal the phenomenon that the gain in economy of description can be arbitrary. In the latter case there is no recursive function serving as upper bound. We discuss developments relevant to the descriptional complexity of formal systems. The results presented are not proved but we merely draw attention to the big picture and some of the main ideas involved.

Partial words are sequences that may have some undefined positions denoted by ⋄'s, where a ⋄ matches every letter of the alphabet. This chapter is related to the problem of characterizing the two-element unavoidable sets of partial words over an arbitrary alphabet, which reduces to the problem of characterizing the unavoidable sets of the form

where a, b are distinct letters of the alphabet and m₁,…, m_k, n₁, …, n_l are nonnegative integers. We prove a conjecture regarding the case k = 1, l = 2,which was identified by Blanchet-Sadri et al. that, if proven, suffices to classify all sets X_{m1,…,mk|n1,…,nl} such that k ≥ 2, l ≥ 2 as avoidable or unavoidable, and which involves six systems of inequalities on m, n₁ and n₂. We classify some of the previously unclassified sets by identifying common two-sided infinite avoiding words and exhibiting exactly which sets these words can avoid. In the process, we introduce a new technique to reduce a set if the period of an avoiding word is known. Finally using Cayley graphs, we are able to classify all remaining sets.

The following sections are included:

• Introduction

• Definitions
  • Classical Notions
  • Extended Glushkov Construction
  • Normal Forms and Casting Operation
  • Characterization of Glushkov Automata in the Boolean Case
  • The Problem of Reduction Rules

• Acyclic Glushkov WFA Properties
  • 𝕂-rules
  • Confluence for 𝕂-rules
  • 𝕂-reducibility
  • Several Examples of Use for 𝕂-rules

• Glushkov 𝕂-graph with Orbits

• Algorithm for Orbit Reduction

• Conclusion

• References

The following sections are included:

• Dictionaries as Finite Automata
  • Simple and Complex, Static and Dynamic
    • Implementing a Dictionary
    • Variants of Finite-State Machines Relevant to Dictionary Data Structure Implementation
      • Deterministic Finite-State Automaton
      • Trie
      • Minimal Deterministic Finite Automaton
      • Recursive Automaton
      • Nondeterministic FA and ε — NDFA
      • Transducer
      • Implementing Dictionaries with FSMs
  • Automata as Mappings
    • Perfect Hashing
    • Morphological Analysis and Synthesis
    • Spelling Correction and Restoration of Diacritics
    • Gazetteers and Information Extraction
      • Pure DFA Approach
      • Indexing Automaton Approach
  • Construction Methods
    • Construction from Strings
    • Construction from Strings with Some Cyclic Structures
    • Construction from Smaller Automata
    • Construction from Other Sources
  • Internal Structure and Compression
    • Representation of Automata
      • Transition Matrix
      • Transition Lists
      • Compressed Transition Matrix
      • Comparison
    • Compression Techniques
      • A Space Optimized Representation of RA
      • Dictionary Compression
      • Compact Representation of Dynamic Dictionaries
    • Conclusions and Further Reading

• References

The following sections are included:

• Introduction
  • Motivation
  • Scope and Outline

• Preliminaries
  • Regular Expressions
  • Trees and Forests
  • XML Basics

• Regular Forest Languages
  • Specifying Regular Forest Languages
    • Forest Grammars
    • Practical Extensions
    • Forest Grammars and XML Schema Languages
  • Recognizing Regular Forest Languages
    • Pushdown Forest Automata
    • From Forest Grammars to Pushdown Forest Automata
  • Bibliographic Notes

• Grammar Queries
  • Specifying Queries
    • Unary Queries
    • K-ary Queries
  • Expressive Power of Grammar Queries
  • Recognizing Unary Queries
    • Pushdown Forest Automata as Relabelings
    • Locating Unary Matches
  • Recognizing Binary Queries
    • Recognizing Simple Binary Queries
    • Recognizing General Binary Queries
  • Recognizing K-ary Queries
  • Implementation Issues
  • Bibliographic Notes
    • Forest Grammar Queries
    • XPath Evaluation and Expressiveness
    • Query Automata
    • Selecting Tree Automata
    • Attribute Grammar Queries
    • Regular Hedge Expressions
    • Tree-walking Automata
    • Pure Logic Formalisms
    • Numerical Document Queries
    • Tree Queries

• Practical Application: A Pattern Language for XML Querying
  • Paths
    • Regular Path Expressions
    • Boolean Connectives for Paths
  • Qualifiers
    • Structure Qualifiers
    • Context Qualifiers
  • Binary Patterns
  • From Patterns to Grammar Queries
  • Comparison with XPath
    • XPath's Paths
    • XPath's Qualifiers
    • Differences in Expressiveness
  • Bibliographic Notes

• Online Querying
  • Right-ignoring Queries
  • Arbitrary Queries
    • Idea
    • Recognizing Matches
    • Complexity
  • Bibliographical Notes

• Summary and Outlook

• Proofs of Theorems
  • Proof of Theorem 5.21
    • Proof of (i₁)
    • Proof of (i₂)
  • Proof of Theorem 5.22
  • Proof of Theorem 5.32

• References

In this chapter, we discuss fundamental mathematical abstractions which can be used to capture and analyse operational semantics of concurrent systems. We focus our attention on the issues involved in the description of runs or behaviours of such systems. Assuming the discrete nature of system executions, in the most basic case, they can be represented as sequences of symbols, each symbol corresponding to the execution of a basic atomic action. By taking into account only the essential causal relationships between the executed actions one can then group together different runs which only differ by the ordering of causally unrelated actions. In the resulting model of Mazurkiewicz traces, each abstract execution (trace) is an equivalence class of the quotient monoid of sequential executions which can be represented by a (causal) partial order on the actions involved in these executions. Starting from this initial setting, the chapter then considers behaviours which are (step) sequences of sets of simultaneously executed actions, and takes into account other relationships between pairs of executed actions, such as weak causality. The resulting abstract behaviours can again be expressed in terms of suitable quotient monoids of step sequences or, equivalently, relational structures generalising causal partial orders. We then show how concrete system models coming from the Petri net domain can be treated using the above abstract notions of concurrent behaviour.

In this work we investigate the learning model in which a learner gets information of the hidden concept by using different types of correction queries (CQs). Specifically, three types of queries are taken into account, the so-called prefix, length bounded and edit distance CQs. In order to state the power of these models, we have considered two learning scenarios. In the first one, computational complexity issues are neglected and the matter is to decide, for a given class of concepts, whether learning in a finite number of steps is possible. We show power relationships among CQ models themselves, between these models and well-established query models, and with learning models in a different paradigm, namely the Gold-style learning in the limit model.

The last part of this chapter is focused on the second learning scenario where computational complexity issues are important. We provide new polynomial time learning algorithms using prefix correction queries for the class of pattern languages and the class of k-reversible languages. In addition, we show power relationships among the new models themselves and the membership query model.

In this chapter, application of grammatical inference to facilitate development of domain-specific languages (DSLs) is presented. Grammatical inference techniques have been applied to infer DSL grammar from DSL programs. Such a scenario would be feasible when domain experts can provide complete DSL programs or excerpts of such programs. The results of grammatical inference, namely the inferred grammar, can be directly used to generate the DSL parser or be further examined by a software language engineer with the aim to further enhance the design of the language. To achieve this goal we developed a memetic algorithm which enables incremental grammar inference. It is a population based evolutionary algorithm enhanced with local search and a generalization phase. Some examples of DSLs from which grammars have been successfully inferred from positive samples are presented.

The following sections are included:

• Introduction

• Definitions
  • Insertion-Deletion Systems
  • Graph-Controlled Insertion-Deletion Systems

• Basic Simulation Principles

• Insertion-Deletion Systems with Rules of Small Size

• Context-Free Insertion-Deletion Systems
  • Non-completeness Results

• One-Sided Contextual Insertion-Deletion Systems
  • Non-completeness Results

• Pure Insertion Systems

• Graph-Controlled Insertion-Deletion Systems

• Graph-Controlled Insertion-Deletion Systems with Priorities

• Bibliographical Remarks

• References

The following sections are included:

• Introduction

• Basic Definitions
  • Preliminaries
  • Accepting Networks of Evolutionary Processors
  • Accepting Networks of Evolutionary Processors with Filtered Connections
  • Timed Accepting Networks of Evolutionary Processors
  • Computational Complexity Classes

• Computational Power
  • Computational Power of ANEPs/ANEPFCs
  • The Role of Evolutionary Operations in ANEPs
  • Complexity Classes and Size Complexity

• Universal ANEPs and ANEPFCs

• A Direct Simulation

• Accepting Networks of Splicing Processors
  • Computational Power and Complexity Results for ANSPs/ANSPFCs

• Problem Solving with ANEPs/ANEPFCs

• Accepting Networks of Picture Processors
  • Pictures and Picture Languages
  • Picture Processors
  • Accepting Networks of Evolutionary Picture Processors
  • Computational Power
  • Solving Picture Matching with ANEPPs

• References

We study the phenomenon of periodicity on quantum automata from three points of view. First, we provide an efficient algorithm for testing the periodicity of stochastic events induced by measure-once one-way unary quantum automata (1qfa's). Second, we design an algorithm for the synthesis of succinct unary 1qfa's inducing periodic events. To evaluate the size of the resulting 1qfa's, we relate the number of states of a minimal 1qfa inducing a linear approximation of a periodic event p to the harmonic structure of p. Next, we study the complexity of our synthesis algorithm. Third, we apply our synthesis algorithm for building succinct 1qfa's that accept unary periodic languages. We also prove a lower bound on the size of 1qfa's accepting unary periodic languages.

The study of various network related processes has recently become a key issue in many science disciplines including biology, chemistry, and physics, but also in sociology and other areas dealing with intensive communication. Different models are sought to describe such processes, among which automata appear to be successful candidates.

Percolation processes, in particular, are of distinguished interest, and the results reported in this paper deal with a special process of this nature. A state of the network is represented by a matching of the underlying graph, while state transitions are induced by certain alternating walks in the network. This model was introduced in 1990 by Dassow and Jurgensen under the name soliton automaton, with the aim to capture the phenomenon of molecular switching.

Soliton graphs and automata have since been studied in the context of matching theory by the authors in a series of works. The present paper is mainly a review of the most important results originating from this study, and it also outlines some future perspectives and generalizations of this interesting model.

In a typical human population, some features of the language are bound to be in flux. Variation in each individual's usage rates of optional features reflects language change in progress. Sociolinguistic surveys have determined that some individuals use new features to a greater degree than the population average, that is, they seem to be leading the change. This article describes a mathematical model of the spread of language change inspired by a model from population genetics. It incorporates the premise that some individuals are linguistic leaders and exert more influence on the speech of learning children than others. Using historical data from the rise of do-support in English, a maximum likelihood calculation yields an estimate for the influence ratio used in the model. The influence ratio so inferred indicates that 19 of the 200 simulated individuals account for 95% of the total influence, confirming that language change may be driven by a relatively small group of leaders. The model can be improved in any number of ways, but additional features must be selected carefully so as not to produce a computationally intractable inference problem. This project demonstrates how data and techniques from different subfields of linguistics can be combined within a mathematical model to reveal otherwise inaccessible information about language variation and change.

In genetic epidemiology, modeling Linkage Disequilibrium (LD) between Single Nucleotide Polymorphisms (SNP) has become an important problem for disease genes mapping. On the fine scale of high-density maps, the complex diseases are often related to effects of combinations of multiple SNPs while the main effects of the pairwise LD measure may be small or absent. The major challenge of association study, especially at the whole-genome level, is the lack of multilocus LD analysis. This chapter introduces Variable Length Finite Automata (VLFA) for describing multilocus LD. Given a set of haplotype-phenotype data, we propose a novel method and algorithm to infer the structure of VLFA. This VLFA consists of an inhomogeneous variable length Markov chain in which the length of memory of the model depends on the nature of stochastic data. The model will have a longer memory if the SNP markers are in the regions of high LD, whereas, the memory will be short in the regions of low LD. Having a stochastic structure, the VLFA reflects the multilocus LD, the dependence structure of haplotypes, the historical recombination events and the location of disease mutations. Through the experimental results on real published SNP data set, we show that our approach is flexible and robust for genetic association studies.

The following sections are included:

• Author Index

• Subject Index