A complete system of B-rational identities
[For the entire collection see Zbl 0758.00017.] Recently we solved two conjectures of \textit{J. H. Conway} [Regular algebras and finite machines, Chapman \& Hall (1971; Zbl 0231.94041)]: a) the monoid identities completed with two other identities from a complete systems, and b) the system obtained by only considering the identities associated with the finite groups is equivalent to the system associated with the finite monoids. Proving then the completeness of them and hence giving the first ``good described complete identities systems for usual rational expressions. The proofs of these results will be published in [\textit{D. Krob}, Theor. Comput. Sci. 89, No. 2, 207-343 (1991; Zbl 0737.68053)]. The paper is essentially a presentation of the methods we used in [\textit{D. Krob}, loc. cit.] to obtain our results. Since the proofs of the main theorems are quite long, we just sketch them here and we refer to [\textit{D. Krob}, loc. cit.] for the complete proofs. It is also to be noticed that the techniques we developed (specially our proof of theorem III.2 restricted to aperiodic semigroups) permitted us to give a new proof of Schützenberger's classical characterization of star-free languages [cf. \textit{G. Lallement}, Combinatorial semigroups theory, Wiley (1979); \textit{J. E. Pin}, Variétés de langages formels,Masson (1984; Zbl 0636.68093); \textit{M. P. Schutzenberger}, Inform. and Control 8, 190-194 (1965)].
- Complete systems of \(\mathcal B\)-rational identities
- Equational properties of fixed point operations in Cartesian categories: an overview
- Algorithms for Kleene algebra with converse
- Container of (min,+)-linear systems
- scientific article; zbMATH DE number 7204945 (Why is no real title available?)
- Equational properties of fixed-point operations in Cartesian categories: an overview
- Coinduction: automata, formal proof, companions (invited paper)
- Concurrent NetKAT. Modeling and analyzing stateful, concurrent networks
- Completeness and the finite model property for Kleene algebra, reconsidered
- An elementary proof of the FMP for Kleene algebra
- On propositional program equivalence (extended abstract)
- A completeness theorem for probabilistic regular expressions
- A proof theory of right-linear ( -)grammars via cyclic proofs
- A proof theory of ( -)context-free languages, via non-wellfounded proofs
- Representations. A meta-model for system analysis
This page was built for publication: A complete system of B-rational identities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038681)
