Results 1 to 10 of about 184 (122)
On the Syntactic Monoids Associated with a Class of Synchronized Codes [PDF]
The Scientific World Journal, 2013 A complete code C over an alphabet A is called synchronized if there exist x,y∈C* such that xA*∩A*y⊆C*. In this paper we describe the syntactic monoid Syn(C+) of C+ for a complete synchronized code C over A such that C+, the semigroup generated by C, is ...
Shou-feng Wang
doaj +8 more sources
A Categorical Approach to Syntactic Monoids [PDF]
Logical Methods in Computer Science, 2018 The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category $\mathcal D$. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of ...
Jiří Adamek +2 more
doaj +7 more sources
The syntactic monoid of an infix code [PDF]
Proceedings of the American Mathematical Society, 1990 Necessary and sufficient conditions on a monoid M M are found in order that M M be isomorphic to the syntactic monoid of a language L L over an alphabet X X having one of the following properties. In the first theorem L L is a P L
Petrich, Mario, Thierrin, Gabriel
openaire +3 more sources
Syntactic Monoids in a Category [PDF]
, 2015 The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category D. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott (D = sets), the syntactic semirings of Polak (D = semilattices), and the syntactic associative ...
Adamek, Jiri +2 more
+7 more sources
Hypercodes, right convex languages and their syntactic monoids [PDF]
Proceedings of the American Mathematical Society, 1981 If X* is the free monoid generated by the alphabet X, then any subset L of X* is called a language over X. If PL is the principal congruence determined by L, then the quotient monoid syn(L) = X*/PL is called the syntactic monoid of L. A hypercode over X is any set of nonemtpy words that are noncomparable with respect to the embedding order of X*.
G. Thierrin
openaire +3 more sources
On deterministic finite automata and syntactic monoid size [PDF]
Theoretical Computer Science, 2003 We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of \(n\)-state (minimal) deterministic finite automata. We show tight upper and lower bounds on the syntactic monoid size depending on the number of generators (input alphabet size) used.
Holzer, Markus, König, Barbara
+7 more sources
The syntactic monoid of the semigroup generated by a maximal prefix code [PDF]
Proceedings of the American Mathematical Society, 1996 Considered are prefix codes which probably represent the class of relatively general codes [\textit{J. Berstel} and \textit{D. Perrin}, Theory of codes, Academic Press, New York (1985; Zbl 0587.68066); \textit{M. Petrich}, Introduction to semigroups, Merrill, Columbus (1973; Zbl 0321.20037)].
Petrich, Mario +2 more
openaire +2 more sources
First-Order Quantifiers and the Syntactic Monoid of Height Fragments of Picture Languages [PDF]
, 2012 We investigate the expressive power of first-order quantifications in the context of monadic second-order logic over pictures. We show that k+1 set quantifier alternations allow to define a picture language that cannot be defined using k set quantifier alternations preceded by arbitrarily many first-order quantifier alternations. The approach uses, for
Oliver Matz
openaire +3 more sources
The syntactic monoid of hairpin-free languages
Acta Informatica, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Kari, Lila +2 more
openaire +3 more sources
Groups in the syntactic monoid of a composed code
Journal of Pure and Applied Algebra, 1986 It is proved: Let Y and Z be codes (with Z finite) and let \(X=Y\circ Z\). Then every group in \(M(X^*)\), the syntactic monoid of \(X^*\), divides a generalized wreath product \((G_ 1\times...\times G_ n)\square H\), where \(G_ 1,...,G_ n\) are groups dividing \(M(Y^*)\) and H is a group dividing \(M(Z^*)\).
Pascal Weil
openaire +2 more sources