Results 81 to 90 of about 184 (122)
ON GROUPS WHICH ARE SYNTACTIC MONOIDS OF DETERMINISTIC CONTEXT-FREE LANGUAGES
International Journal of Algebra and Computation, 2004 The author shows that the class of groups which are syntactic monoids of deterministic context-free languages is closed under restricted standard wreath products with virtually free top groups. This provides an answer to a question of T. Herbst.
Claas E. Röver
openaire +3 more sources
, 1991 Abstract In this chapter we obtain another characterization of rational languages in terms of a monoid Syn(L), called the syntactic monoid of L, associated with every L ⊆ A*. The computation of Syn(L) is then discussed, via a notion important in its own right, namely the minimal automaton of L.
John Howie
openaire +2 more sources
On?-Languages whose syntactic monoid is trivial
International Journal of Computer & Information Sciences, 1983 For a languageL the syntactic monoid SynL is trivial if and only if indeedL itself is trivial, that isL = O orL=X*. As a surprise one realizes that the syntactic monoid SynL of an ω-languageL being trivial by no means implies thatL be trivial. This situation is analyzed in this paper.
H. J�rgensen, G. Thierrin
openaire +2 more sources
Syntactic monoids in the construction of systolic tree automata
International Journal of Computer & Information Sciences, 1985 A regular language L can be accepted by a systolic tree automaton where the processors at each node of the underlying binary tree are capable of computing the product of two elements in the syntactic monoid of L. This construction gives rise to certain minimization problems which are studied in this paper.
Jürgensen, H., Salomaa, A.
openaire +3 more sources
The syntactic monoid of the semigroup generated by a comma-free code
Proceedings of the Royal Society of Edinburgh: Section A Mathematics, 1995 A sequence of lemmas leads to a two-fold characterisation of the syntactic monoid in the title. Some alternatives as well as special cases, in particular when the code consists of a singleton, are considered.
Petrich, Mario, Reis, C. M.
openaire +2 more sources
On the word problem for syntactic monoids of piecewise testable languages
Semigroup Forum, 2011 Piecewise testable languages are widely studied area in the theory of automata. We analyze the algebraic properties of these languages via their syntactic monoids. In this paper a normal form is presented for 2- and 3-piecewise testable languages and a log-asymptotic estimate is given for the number of words over these monoids.
Kátai-Urbán Kamilla +4 more
openaire +2 more sources
Syntactic complexity of context-free grammars over word monoids
Acta Informatica, 1996 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Alexander Meduna
openaire +3 more sources
Subgroups of syntactic monoids of finite inverse biprifix codes
, 2000 Finite biprefix codes whose syntactic monoids are groups were studied by M.P. Schutzenberger. P. Udomkavanich gave a characterization of finite inverse biprefix codes (codes admitting finite inverse semigroups as their syntactic monoids). An example of finite inverse biprefix code whose syntactic monoid contains a nonabelian group, S3, was given.
Khajee Jantarakhajorn +1 more
openaire +2 more sources
A Syntactic Approach to the MacNeille Completion of Λ∗, the Free Monoid Over an Ordered Alphabet Λ
Order, 2018 Let Λ∗ be the free monoid of (finite) words over a not necessarily finite alphabet Λ, which is equipped with some (partial) order. This ordering lifts to Λ∗, where it extends the divisibility ordering of words. The MacNeille completion of Λ∗ constitutes a complete lattice ordered monoid and is realized by the system of “closed” lower sets in Λ ...
Hans-Jürgen Bandelt, Maurice Pouzet
openaire +3 more sources
An algebraic framework for the study of the syntactic monoids application to the group languages
, 1976 We study here a category whose objects are the pairs (M,P) where M is a monoid and P a subset of M. This gives a suitable algebraic framework for studying the relationships between the properties of a language and those of its syntactic monoid, specially in the case of the infinite syntactic monoids as we did in [12, 13, 14].
Jacques Sakarovitch
openaire +2 more sources