Results 11 to 20 of about 157,848 (165)
On Croisot - languages and Dubreil - languages having a group as syntactic monoid.
Journal of Computer Science and Cybernetics, 2012 Lê Quốc Hán, Hồ Tiến Dương
semanticscholar +5 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
+6 more sources
Nondeterministic Syntactic Complexity [PDF]
Foundations of Software Science and Computation Structures24th International Conference, 2021 We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any
Myers R, Milius S, Urbat H.
europepmc +2 more sources
Piecewise testable tree languages [PDF]
Logical Methods in Computer Science, 2012 This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination
Mikołaj Bojańczyk +2 more
doaj +7 more sources
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership [PDF]
Logical Methods in Computer Science, 2020 We study two extensions of FO2[
Andreas Krebs +3 more
doaj +4 more sources
Similarities of Jonsson spectra’s classes
Қарағанды университетінің хабаршысы. Математика сериясы, 2023 The study of syntactic and semantic properties of a first-order language, generally speaking, for incomplete theories, is one of the urgent problems of mathematical logic.
A.R. Yeshkeyev +2 more
doaj +2 more sources
Recognizing splicing languages: Syntactic monoids and simultaneous pumping
Discrete Applied Mathematics, 2006 AbstractWe use syntactic monoid methods, together with an enhanced pumping lemma, to investigate the structure of splicing languages. We obtain an algorithm for deciding whether a regular language is a reflexive splicing language, but the general question remains open.
Elizabeth Goode, Dennis Pixton
openalex +3 more sources
On Deterministic Finite Automata and Syntactic Monoid Size [PDF]
, 2003 We continue our investigation on the relationship between regular languages and syntactic monoid size. In this paper we confirm the conjecture on two generator transformation semigroups. We show that for every prime n ≥ 7 there exist natural numbers k and l with n = k + l such that the semigroup Uk, l is maximal w.r.t.
Markus Holzer, Barbara König
+5 more sources
First-Order Quantifiers and the Syntactic Monoid of Height Fragments of Picture Languages
, 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
openalex +4 more sources
Biprefix codes, inverse semigroups and syntactic monoids of injective automata
Theoretical Computer Science, 1984 The author proves some properties of automata and semigroups. He shows that each injective automaton may be simulated by the minimal automaton of a language of the form \(B^*\), B a finite biprefix code. A similar result holds for any automaton, with ''biprefix'' replaced by ''prefix''.
T. E. Hall
openalex +4 more sources