Search

In this paper, n-PS-codes, 2-infix-outfix codes and some related classes of codes are investigated where n ≥ 1 . The classes of n-PS-codes and 2-infix-outfix codes are generalizations of classes of prefix codes and suffix codes, and infix codes and outfix codes, respectively. The closure properties of n-PS-codes and g-3-PS-codes under composition are discussed where n ≥ 1 , and the condition under which the class of 2-infix-outfix codes is closed under composition is provided. [ABSTRACT FROM AUTHOR]

In the fields of combinatorics on words and theory of codes, a two-word language { x , y } is a code if and only if x y ≠ y x . But up to now, corresponding characterizations for a three-word language, which forms a code, have not been completely found. Let X = { x , y , z } be a three-word language and | x | , | y | , | z | be their lengths. When | x | = | y | < | z | , a necessary and sufficient condition for X to be a code was obtained in 2018. If | x | < | y | = | z | ≤ 2 | x | , a necessary and sufficient condition for X to be a code is proposed in this paper. [ABSTRACT FROM AUTHOR]

This paper explains how any nondeterministic automaton for a regular language L gives rise to a one-dimensional oriented topological quantum field theory (TQFT) with inner endpoints and zero-dimensional defects labeled by letters of the alphabet for L. The TQFT is defined over the Boolean semiring B . Different automata for a fixed language L produce TQFTs that differ by their values on decorated circles, while the values on decorated intervals are described by the language L. The language L and the TQFT associated with an automaton can be given a path integral interpretation. In this TQFT, the state space of a one-point 0-manifold is a free module over B with the basis of states of the automaton. Replacing a free module by a finite projective B -module P allows to generalize automata and this type of TQFT to a structure where defects act on open subsets of a finite topological space. Intersection of open subsets induces a multiplication on P allowing to extend the TQFT to a TQFT for one-dimensional foams (oriented graphs with defects modulo a suitable equivalence relation). A linear version of these constructions is also explained, with the Boolean semiring replaced by a commutative ring. [ABSTRACT FROM AUTHOR]

In this paper we go further with the study initiated by Behle, Krebs and Reifferscheid (in: Proceedings CAI 2011, Lecture Notes in Computer Science, vol 6742, pp 97–114, 2011), who gave an Eilenberg-type theorem for non-regular languages via typed monoids. We provide a new extension of that result, inspired by the one carried out by Pin in the regular case in 1995, who considered classes of languages not necessarily closed under complement. We introduce the so-called positively typed monoids, and give a correspondence between varieties of such algebraic structures and positive varieties of possibly non-regular languages. We also prove a similar result for classes of languages with weaker closure properties. [ABSTRACT FROM AUTHOR]

The construction of thin maximal bifix codes of degree 1 or 2 is clear and simple. In this paper, a class of thin maximal bifix codes of degree 3 which contains all finite maximal bifix codes of degree 3 is investigated. The construction of such codes is determined. It is well known that for any positive integers d and k, there are finitely many finite maximal bifix codes of degree d over a k-letter alphabet. But the enumeration problem is unsolved in general. In this paper, we show that for any positive integer k, there is a bijection from the set of all finite maximal bifix codes of degree 3 over a k-letter alphabet onto the set of all directed acyclic graphs with k vertices, and then, the enumeration problem of finite maximal bifix codes of degree 3 is solved. [ABSTRACT FROM AUTHOR]

Suppose that L is a nonempty language over A, k ∈ N 0 and m ∈ N . If L satisfies (L A k) m L ∩ A + (L A k) m - 1 L A + = ∅ , then L is a code and is called a (k, m)-comma code. If L is a (k, m)-comma code, then it is known that L is an infix code when m = 1 and L is a bifix code when m ≥ 1 . In this paper, we extend the study and find that the class of (k, m)-comma codes and the class of infix codes are incomparable but they are not disjoint, so we first characterize the (k, m)-comma codes with m ≥ 2 which are infix codes. We also describe the solid codes with minimum lengths greater than k and the 2-(k, 1)-comma codes by different approaches. Finally, the class of bifix codes will be classified into disjoint union of some subclasses and a criterion to determine the subclass membership of a given bifix code will be given. [ABSTRACT FROM AUTHOR]

In a previous paper, the authors have shown that Eilenberg's variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower. [ABSTRACT FROM AUTHOR]

It is always an interesting subject to investigate whether a three-element language is a code or not. In this paper, we consider a special class of three-element languages, where two words have the same length which is less than the length of the third word. We give a necessary and sufficient condition to state whether a three-element language in this class is a code. This result partially resolves the problem proposed by Professor H. J. Shyr in 1990s. [ABSTRACT FROM AUTHOR]

Abstract: The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one. We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with , let . Let , let be the number of factors in the prime factorization of n. We give an algorithm to decide whether there exists n, with , and a finite maximal code C which is also factorizing such that . We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in satisfy a property defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set can be embedded in a set satisfying . Furthermore, we prove that, conversely, for each set satisfying , under additional hypotheses, there exists a factorizing code C such that and, as a consequence, is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each , we have , with . In addition, we prove that there exist sets which satisfy and which are not codes. [Copyright &y& Elsevier]

This paper studies nested simulation and nested trace semantics over the language BCCSP, a basic formalism to express finite process behaviour. It is shown that none of these semantics affords finite (in)equational axiomatizations over BCCSP. In particular, for each of the nested semantics studied in this paper, the collection of sound, closed (in)equations over a singleton action set is not finitely based. [Copyright &y& Elsevier]

Automaticity is an important concept in group theory as it yields an efficient solution to the word problem and provides other possibilities for effective computation. The concept of automaticity generalizes naturally from groups to monoids and semigroups and the efficiency of the solution of the word problem is preserved when we do this. Whilst this subject has been studied extensively (in both the group and the monoid/semigroup case), there are still some deep and major open problems, including questions concerning the automaticity of certain naturally occurring classes of groups, monoids and semigroups. In this paper, we consider two such classes of monoids, namely the positive singular Artin monoids of finite type and the singular Artin monoids of the finite type. The main purpose here is to show that these monoids are all automatic. When establishing the automaticity of monoids, one obstacle is that we often have asynchronous finite automata recognizing multiplication and we need to establish the existence of synchronous machines accomplishing the same task. Building on the work of Frougny and Sakarovitch, we establish a new criterion for achieving such a transition; this is fundamental in the establishment of the automaticity of the monoids we consider here and may well apply to other naturally occurring classes of monoids and semigroups as well. [ABSTRACT FROM AUTHOR]

Abstract: Synthetic Domain Theory (SDT) was originally suggested by Dana Scott as a uniform and logic based account of domain theory. In SDT the domain structure is intrinsic to a chosen class of sets with “good” properties. General SDT has a lot of different models which differ w.r.t. the ambient logic but also w.r.t. the PCF hierarchy, i.e. the finite type hierarchy over the partial natural numbers. From the early days of SDT we know satisfactory axiomatizations of SDT à la Scott which enforce the existence of “parallel or”. A realizability model for SDT where the PCF hierarchy coincides with the strongly stable model of Bucciarelli and Ehrhard has been found independently by van Oosten (1999) and Longley (2002) . Their model is based on the typed partial combinatory algebra of concrete data structures and sequential algorithms. In this paper, we try to axiomatize this kind of Sequential SDT for the first time. Our approach is based on replacing by , the observably sequential algorithms, as suggested by Cartwright et al. (1994) . The axioms are inspired by the realizability model over and its type of observations with two global elements standing for nontermination and termination with error, respectively. Unlike in traditional domain theory this type is not a dominance because binary infimum is not available as an operation. This forces us to adapt some of the basic machinery of SDT. [Copyright &y& Elsevier]

Abstract: A bialgebra is a structure which is simultaneously an algebra and a coalgebra, such that the algebraic and coalgebraic parts are compatible. Bialgebras are usually studied over a commutative ring. In this paper, we apply the defining diagrams of algebras, coalgebras, and bialgebras to categories of semimodules and semimodule homomorphisms over a commutative semiring. We then treat automata as certain representation objects of algebras and formal languages as elements of dual algebras of coalgebras. Using this perspective, we demonstrate many analogies between the two theories. Finally, we show that there is an adjunction between the category of “algebraic” automata and the category of deterministic automata. Using this adjunction, we show that -linear automaton morphisms can be used as the sole rule of inference in a complete proof system for automaton equivalence. [Copyright &y& Elsevier]

Abstract: Length preserving morphisms and inverse of substitutions are two well-studied operations on regular languages. Their connection with varieties generated by power monoids was established independently by Reutenauer and Straubing in 1979. More recently, an ordered version of this theory was proposed by Polák and by the authors. In this paper, we present an improved version of these results and obtain the following consequences. Given a variety of finite ordered monoids , let be the variety of finite ordered monoids generated by the upper set monoids of members of . Then . This contrasts with the known results for the unordered case: the operator corresponding to power monoids satisfies , but the varieties , , and can be distinct. [Copyright &y& Elsevier]

In this paper, we introduce a class of generalized regular languages, namely PS-regular languages, and give some characterizations of such generalized regular languages. As applications of the results, we obtain some characterizations of regular languages. Also, we consider the closure properties of the class of PS-regular languages, and the relationship among PS-regular languages, context-free languages and context-sensitive languages. [ABSTRACT FROM AUTHOR]

In this paper, we study a generalization of the classical notions of language equations: involution language equations. This notion is motivated by DNA strand design where Watson-Crick complementarity can be modular as an antimorphic involution function. Characterizations of words u and languages A and B which satisfy the equation θ(u)B=Au are obtained. For a language L, solutions of the equation θ(L)B=AL are considered. We also study the characteristics of Lθ-commutative equivalent languages. [ABSTRACT FROM AUTHOR]

A language A is left cancellative if from AB=AC, it follows that B=C, for any two languages B and C. Semi-singular and inf-singular languages are two disjoint sub-sets of left cancellative languages and are introduced by Hsieh and Shyr [Left cancellative elements in the monoid of languages, Soochow J. Math. 4 (1978), pp. 7-15]. In this paper, we further study them. It is shown that all non-dense and all maximal left cancellative languages are semi-singular while all right dense left cancellative languages are inf-singular. Finally, a theorem shows that there is a left cancellative language which is neither semi-singular nor inf-singular. [ABSTRACT FROM AUTHOR]

In this paper, we describe safety semantics as abstract interpretation of a trace-based operational semantics of a transition system. Intuitively, a property is safety if 'nothing bad will happen'. Formally this is described by saying that a property is safety if it is maximal with respect to a given set of allowed partial executions. We show that this can be specified in the standard Cousot's framework of abstract interpretation. In particular, we show that this semantics can be derived as fixpoint of a semantic operator. This construction provides a formal characterization of the constructive nature of safety properties, that can be enforced by means of execution monitors. By using the same construction, we show that while safety without stuttering preserves the constructive nature, safety properties allowing cancellation of states lose the constructive characterization. Finally, we characterize safety properties as the closed elements of a closure, and we show that in the abstract interpretation framework safety and liveness properties lose their complementary nature. [ABSTRACT FROM AUTHOR]

An ω-language over a finite alphabet X is a set of infinite sequences of letters of X. An ω-language L is P-disjunctive if Pω, L is the equality, where Pω, L is the congruence on X* introduced by L. We prove that L contains a P-disjunctive ω-language if and only if L is P-dense. In order to determine whether a given ω-language is P-disjunctive or not, the concept of P-disjunctive domains is defined in this paper. And it is showed that P-disjunctive domains are equivalent to disjunctive domains. [ABSTRACT FROM AUTHOR]

Abstract: This paper shows that bisimulation equivalence does not afford a finite equational axiomatization over the language obtained by enriching Bergstra and Klop''s basic process algebra (BPA) with the interrupt operator. Moreover, it is shown that the collection of closed equations over this language is also not finitely based. In sharp contrast to these results, the collection of closed equations over the language BPA enriched with the disrupt operator is proven to be finitely based. [Copyright &y& Elsevier]

Abstract: This paper studies 3-polygraphs as a framework for rewriting on two-dimensional words. A translation of term rewriting systems into 3-polygraphs with explicit resource management is given, and the respective computational properties of each system are studied. Finally, a convergent 3-polygraph for the (commutative) theory of -vector spaces is given. In order to prove these results, it is explained how to craft a class of termination orders for 3-polygraphs. [Copyright &y& Elsevier]

Abstract: This paper confirms a conjecture of Bergstra and Klop''s from 1984 by establishing that the process algebra obtained by adding an auxiliary operator proposed by Hennessy in 1981 to the recursion free fragment of Milner''s Calculus of Communicating Systems is not finitely based modulo bisimulation equivalence. Thus, Hennessy''s merge cannot replace the left merge and communication merge operators proposed by Bergstra and Klop, at least if a finite axiomatization of parallel composition modulo bisimulation equivalence is desired. [Copyright &y& Elsevier]