Rational sets in commutative monoids
From MaRDI portal
Publication:2542523
DOI10.1016/0021-8693(69)90070-2zbMath0206.02703OpenAlexW1971435636MaRDI QIDQ2542523
Schützenberger, Marcel-Paul, Samuel Eilenberg
Publication date: 1969
Published in: Journal of Algebra (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0021-8693(69)90070-2
Related Items
D-finite multivariate series with arithmetic restrictions on their coefficients, Undecidability of the submonoid membership problem for free nilpotent group of class $l\geqslant 2$ of sufficiently large rank, INTERLEAVING LOGIC AND COUNTING, Une hiérarchie des parties rationnelles de N2, On a Theorem of Malcev, On the Petri net realization of context-free graphs, Decidable weighted expressions with Presburger combinators, A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems, Logic and rational languages of scattered and countable series-parallel posets, Nondeterministic Tree Width of Regular Languages, A Proof of Parikh’s Theorem via Dickson’s Lemma, Existence of home states in Petri nets is decidable, Unnamed Item, Holonomic functions and their relation to linearly constrained languages, The synthesis of Petri nets from path-automatic specifications, Complete semi-Thue systems for abelian groups, On positive commutative tomonoids, General solution of systems of linear diophantine equations and inequations, On polynomial ideals, their complexity, and applications, Petri nets, commutative context-free grammars, and basic parallel processes, The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups, Unnamed Item, Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable, On regular trace languages, Unnamed Item, On the size of independent systems of equations in semigroups, A note on some languages in uniform \(ACC^ 0\), Slightly commutative Kleene semigroups, On rationality of verbal subsets in a group, Unnamed Item, Rational and Recognisable Power Series, On the word problem for special monoids, Unnamed Item, Finitely generated left commutative semigroups are residually finite, Unnamed Item, On the rational subset problem for groups., Submonoids and rational subsets of groups with infinitely many ends., Closure properties and complexity of rational sets of regular languages, Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two, EDT0L solutions to equations in group extensions, Criteria to disprove context freeness of collage languages., Sur les ensembles linéaires, Deciding whether a relation defined in Presburger logic can be defined in weaker logics, Tilings and submonoids of metabelian groups., Input- or output-unary sweeping transducers are weaker than their 2-way counterparts, Unique decipherability in the monoid of languages: an application of rational relations, A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups, A polynomial algorithm for solving systems of two linear diophantine equations, Word-mappings of level 2, Presentations for subsemigroups of finitely generated commutative semigroups, On bounded linear codes and the commutative equivalence, Petri net languages and infinite subsets of \(\mathbb{N}^m\), On the commutative equivalence of bounded context-free and regular languages: the code case, On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\), On commutative Kleene monoids, On problems related to growth, entropy, and spectrum in group theory, Logically defined subsets of \(\mathbb{N}{}^ k\), On a kind of Fatou property of context-free groups, A deterministic algorithm to decide if a finitely presented abelian monoid is cancellative, Recursive Petri nets, Undecidability of bisimilarity for Petri nets and some related problems, The submonoid and rational subset membership problems for graph groups., \(\mathbb{N}\)-rationality of zeta functions, An Hadamard operation on rational relations, Verification of population protocols, Learning semilinear sets from examples and via queries, Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity, On the commutative equivalence of bounded context-free and regular languages: the semi-linear case, Sur quelques classes d’applications de $N^2$ dans les ensembles finis, Group presentations, formal languages and characterizations of one- counter groups, On bounded rational trace languages, Two iteration theorems for some families of languages, Rational relations having a rational trace on each finite intersection of rational relations, The set of realizations of a max-plus linear sequence is semi-polyhedral, On semigroups with maximal conditions, Complementation of Branching Automata for Scattered and Countable N-Free Posets, Decidability of performance equivalence for basic parallel processes, Two problems for solvable and nilpotent groups, Local testability from words to traces, a suitable definition, Counting productions in context-free derivations, Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups, Deterministic and unambiguous two-dimensional languages over one-letter alphabet, Complementation of Branching Automata for Scattered and Countable Series-Parallel Posets, Non-commutative Gröbner bases in algebras of solvable type, On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations, Unique Decipherability in the Monoid of Languages: An Application of Rational Relations, Reachability in Petri Nets with Inhibitor Arcs, On Model Checking Boolean BI, Deux applications de la représentation matricielle d'une série rationnelle non commutative. (Two applications of matrix representations of a rational non -commutative series), Unnamed Item, Quasi-polynomials, linear Diophantine equations and semi-linear sets, On the size of independent systems of equations in semigroups, Decision procedure of some relevant logics: a constructive perspective, The Parikh counting functions of sparse context-free languages are quasi-polynomials, Les 1-convexes du monoide commutatif N\(^n\), Sur la rationalite de certaines séries generatrices, Rational subsets of unitriangular groups, Decision problems among the main subfamilies of rational relations, The residue of vector sets with applications to decidability problems in Petri nets, On a valuation of rational subsets of \(Z^{k}\), Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups., Properties of congruences on commutative monoids, Inverse morphic equivalence on languages, Residual finiteness in permutation varieties of semigroups, Complexity of the word problem for commutative semigroups of fixed dimension, Extending regular expressions with iterated shuffle, Rational subsets and submonoids of wreath products., Modelization of deterministic rational relations, An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable, A NOTE ON LIST LANGUAGES, Characterization and complexity results on jumping finite automata
Uses Software
Cites Work
