Criteria for the matrix equivalence of words

This paper investigates the criteria for deciding whether two words are matrix equivalent. Certain upper diagonal matrices, generally referred to as the Parikh matrices, have been widely investigated because of their usefulness in computing the numbers of subword occurrences and thereby characterizing words by numbers. However, apart from the binary alphabet, not much is known about the properties of the matrix equivalent words, that is, words possessing the same matrix. The paper investigates both the general criteria, as well as the criteria valid in natural special cases. An exhaustive solution is obtained for ternary alphabets.     

Enriching Parikh matrix mappings

In this paper, we define the Super-Parikh (S-Parikh) matrix mapping as an extension of the Parikh matrix mapping introduced by Mateescu et al. Like the Parikh matrix, the extension revolves around a certain type of square matrices, but instead of non-negative integers, its matrix-mapped elements are non-negative rationals (fractions). We study the basic properties of the newly defined formalism and later on we investigate the injectivity of the mapping. Also, we begin a search for the reverse mapping – that is a method for obtaining a word, given the S-Parikh matrix.     

Some characterizations of Parikh matrix equivalent binary words

We state different characterizations of pair of words having the same Parikh matrix.     

Extending Parikh matrices

We introduce the notion of Parikh matrix induced by a word, a natural extension to the notion of Parikh matrix and prove a set of properties for this kind of matrices.

We also study the relation between these two notions. We show that combining properties from both we obtain a more powerful tool for proving algebraic properties of words.     

Decision problems concerning thinness and slenderness of formal languages

A language L is called thin if for almost all n there is at most one word of length n in L. A language L is called slender if there is a positive integer k such that for any n there are at most k words of length n in L. The notions of Parikh thin and Parikh slender languages are defined similarly by counting the words with the same Parikh vectors instead of the words of the same length. In this paper we discuss decision problems concerning these four properties. It is shown that all four properties are decidable for bounded semilinear languages but undecidable for DT0L languages. As a consequence all these problems are decidable for context-free languages. Received 9 June 1997 / 3 December 1997     

The equality problem for Parikh simple algebraic power series

A power series r with noncommuting variables is called Parikh simple if no two words in the support of r are commutatively equivalent. We show that equality is decidable for Parikh simple algebraic power series having their coefficients in a computable field.     

Abelian combinatorics on words: A survey

We survey known results and open problems in abelian combinatorics on words. Abelian combinatorics on words is the extension to the commutative setting of the classical theory of combinatorics on words. The extension is based on abelian equivalence, which is the equivalence relation defined in the set of words by having the same Parikh vector, that is, the same number of occurrences of each letter of the alphabet. In the past few years, there was a lot of research on abelian analogues of classical definitions and properties in combinatorics on words. This survey aims to gather these results.     

Tissue P systems with channel states

We consider tissue-like P systems with states associated with the links (we call them synapses) between cells, controlling the passage of objects across the links. We investigate the computing power of such devices for the case of using—in a sequential manner—antiport rules of small weights. Systems with two cells are proved to be universal when having arbitrarily many states and minimal antiport rules, or one state and antiport rules of weight two. Also the systems with arbitrarily many cells, three states, and minimal antiport rules are universal. In contrast, the systems with one cell and any number of states and rules of any weight only compute Parikh sets of matrix languages (generated by matrix grammars without appearance checking); characterizations of Parikh images of matrix languages are obtained for such one-cell systems with antiport rules of a reduced weight.     

融合词簇约束的汉越跨语言词嵌入

针对传统跨语言词嵌入方法在汉越等差异较大的低资源语言上对齐效果不佳的问题,提出一种融合词簇对齐约束的汉越跨语言词嵌入方法。通过独立的单语语料训练获取汉越单语词嵌入,使用近义词、同类词和同主题词3种不同类型的关联关系,充分挖掘双语词典中的词簇对齐信息以融入到映射矩阵的训练过程中,使映射矩阵进一步学习到不同语言相近词间具有的一些共性特征及映射关系,根据跨语言映射将两种语言的单语词嵌入映射至同一共享空间中对齐,令具有相同含义的汉语与越南语词嵌入在空间中彼此接近,并利用余弦相似度为空间中每一个未经标注的汉语单词查找对应的越南语翻译构建汉越对齐词对,实现跨语言词嵌入。实验结果表明,与传统有监督及无监督的跨语言词嵌入方法Multi_w2v、Orthogonal、VecMap、Muse相比,该方法能有效提升映射矩阵在非标注词上的泛化性,改善汉越低资源场景下模型对齐效果较差的问题,其在汉越双语词典归纳任务P@1和P@5上的对齐准确率相比最好基线模型提升了2.2个百分点。     

Connections between subwords and certain matrix mappings

Parikh matrices recently introduced have turned out to be a powerful tool in the arithmetizing of the theory of words. In particular, many inequalities between (scattered) subword occurrences have been obtained as consequences of the properties of the matrices. This paper continues the investigation of Parikh matrices and subword occurrences. In particular, we study certain inequalities, as well as information about subword occurrences sufficient to determine the whole word uniquely. Some algebraic considerations, facts about forbidden subwords, as well as some open problems are also included.     

Commutative grammars

Commutative grammars are a formalism for generating bags, equivalent to vector addition systems and Petri nets. Known results are recalled and new one are presented on reachability and boundedness. In particular some subclasses of commutative grammars are introduced which admit a positive answer to these problems, and generate semilinear languages. Finally the equivalence, via Parikh mapping, of commutative and matrix grammars is proven.     

Subword balance, position indices and power sums

In this paper, we investigate various ways of characterizing words, mainly over a binary alphabet, using information about the positions of occurrences of letters in words. We introduce two new measures associated with words, the position index and sum of position indices. We establish some characterizations, connections with Parikh matrices, and connections with power sums. One particular emphasis concerns the effect of morphisms and iterated morphisms on words.     

Unique Decipherability in the Monoid of Languages: An Application of Rational Relations

We attack the problem of deciding whether a finite collection of finite languages is a code, that is, possesses the unique decipherability property in the monoid of finite languages. We investigate a few subcases where the theory of rational relations can be employed to solve the problem. The case of unary languages is one of them and as a consequence, we show how to decide for two given finite subsets of nonnegative integers, whether they are the nth root of a common set, for some n≥1. We also show that it is decidable whether a finite collection of finite languages is a Parikh code, in the sense that whenever two products of these sets are commutatively equivalent, so are the sequences defining these products. Finally, we consider a nonunary special case where all finite sets consist of words containing exactly one occurrence of the specific letter.     

Parikh?s theorem: A simple and direct automaton construction

Parikh?s theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.     

On Approximate Jumbled Pattern Matching in Strings

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of a Parikh vector q in the text s requires finding a substring t of s with p(t)=q. This can be viewed as the task of finding a jumbled (permuted) version of a query pattern, hence the term Jumbled Pattern Matching. We present several algorithms for the approximate version of the problem: Given a string s and two Parikh vectors u,v (the query bounds), find all maximal occurrences in s of some Parikh vector q such that u≤q≤v. This definition encompasses several natural versions of approximate Parikh vector search. We present an algorithm solving this problem in sub-linear expected time using a wavelet tree of s, which can be computed in time O(n) in a preprocessing phase. We then discuss a Scrabble-like variation of the problem, in which a weight function on the letters of s is given and one has to find all occurrences in s of a substring t with maximum weight having Parikh vector p(t)≤v. For the case of a binary alphabet, we present an algorithm which solves the decision version of the Approximate Jumbled Pattern Matching problem in constant time, by indexing the string in subquadratic time.     

Subword conditions and subword histories

This paper introduces the notion of a subword condition and investigates languages defined by them. The special case, where the language reduces to one word, concerns the inference of a sequence from its subsequences. We obtain various characterization and decidability results for languages defined by subword conditions. The results contribute to the theory of Parikh matrices and arithmetizing the study of words. An important notion from early automata theory, that of a quasi-uniform event, plays a central role in our characterization.     

含不可控变迁的Petri网监控器设计

在基于Petri网建模的含不可控事件的离散事件系统监控器设计中,当给定的控制目标为Parikh矢量约束时,提出通过转换矩阵R将不可控变迁导致的非法不等式约束变换为允许约束,并求得相应监控器.构造矩阵方程求解R,通过矩阵方程的相容性判断R的存在性,并给出利用广义逆矩阵求解R的算法,得到对应的允许约束和监控器.同时提出代价函数,用于寻找控制观测代价最小的监控器.最后通过实例验证了该算法的正确性和有效性.     

针对一般线性约束的Petri网控制器设计方法

针对基于Petri网离散事件系统关于标识向量和Parikh向量的不等式约束反馈控制器设计问题,提出一种新的控制器设计方法.该方法首先利用Petri网的状态方程把关于标识向量和Parikh向量的不等式约束转变成关于Parikh向量的不等式约束,然后基于Petri网库所是关于Parikh向量的不等式约束的观点构造控制器.最后将该方法与Iordache和Moody提出的方法作比较,实验结果显示该方法更简单、有效.     

Appearance-based mapping and localization for mobile robots using a feature stability histogram

The strength of appearance-based mapping models for mobile robots lies in their ability to represent the environment through high-level image features and to provide human-readable information. However, developing a mapping and a localization method using these kinds of models is very challenging, especially if robots must deal with long-term mapping, localization, navigation, occlusions, and dynamic environments. In other words, the mobile robot has to deal with environmental appearance change, which modifies its representation of the environment. This paper proposes an indoor appearance-based mapping and a localization method for mobile robots based on the human memory model, which was used to build a Feature Stability Histogram (FSH) at each node in the robot topological map. This FSH registers local feature stability over time through a voting scheme, and the most stable features were considered for mapping, for Bayesian localization and for incrementally updating the current appearance reference view in the topological map. The experimental results are presented using an omnidirectional images dataset acquired over the long-term and considering: illumination changes (time of day, different seasons), occlusions, random removal of features, and perceptual aliasing. The results include a comparison with the approach proposed by Dayoub and Duckett (2008) [19] and the popular Bag-of-Words (Bazeille and Filliat, 2010) [35] approach. The obtained results confirm the viability of our method and indicate that it can adapt the internal map representation over time to localize the robot both globally and locally.     

Synchronizing Relations on Words

While the theory of languages of words is very mature, our understanding of relations on words is still lagging behind. And yet such relations appear in many new applications such as verification of parameterized systems, querying graph-structured data, and information extraction, for instance. Classes of well-behaved relations typically used in such applications are obtained by adapting some of the equivalent definitions of regularity of words for relations, leading to non-equivalent notions of recognizable, regular, and rational relations. The goal of this paper is to propose a systematic way of defining classes of relations on words, of which these three classes are just natural examples, and to demonstrate its advantages compared to some of the standard techniques for studying word relations. The key idea is that of a synchronization of a pair of words, which is a word over an extended alphabet. Using it, we define classes of relations via classes of regular languages over a fixed alphabet, just {1,2} for binary relations. We characterize some of the standard classes of relations on words via finiteness of parameters of synchronization languages, called shift, lag, and shiftlag. We describe these conditions in terms of the structure of cycles of graphs underlying automata, thereby showing their decidability. We show that for these classes there exist canonical synchronization languages, and every class of relations can be effectively re-synchronized using those canonical representatives. We also give sufficient conditions on synchronization languages, defined in terms of injectivity and surjectivity of their Parikh images, that guarantee closure under intersection and complement of the classes of relations they define.