Recognizable and rational languages of finite and infinite traces
[For the entire collection see Zbl 0753.00019.] We introduce and study recognizable and rational languages of finite and infinite traces. We characterize recognizable languages by means of a syntactic congruence. We prove that the family of recognizable languages is strinctly included in the family of rational languages. Next, we study the closure properties of the family of recognizable languages. We prove that this family is closed under the Boolean operations and under concatenation. Contrary to the (finite) iteration, the infinite iteration of a finite trace is proved to be recognizable. We conclude with some open problems.
- An extension of Kleene's and Ochmański's theorems to infinite traces
- Recognizable trace languages, distributed automata and the distribution problem
- Deterministic asynchronous automata for infinite traces
- Rational and recognizable complex trace languages
- On the complementation of asynchronous cellular Büchi automata
- Classifying recognizable infinitary trace languages using word automata
- Agreeing within a few writes
- A note on the logical definability of rational trace languages
- Factor and Subsequence Kernels and Signatures of Rational Languages
- Classifying recognizable infinitary trace languages using word automata
- scientific article; zbMATH DE number 18901 (Why is no real title available?)
- Recognizable complex trace languages. (Abstract)
- A Kleene theorem for infinite trace languages
- scientific article; zbMATH DE number 512855 (Why is no real title available?)
- Logical definability on infinite traces
- On the complementation of Büchi asynchronous cellular automata
- scientific article; zbMATH DE number 2143013 (Why is no real title available?)
- Subclasses of recognizable trace languages
- Toward a Structure Theory of Regular Infinitary Trace Languages
- Asynchronous cellular automata for infinite traces
- LAZARD'S ELIMINATION (IN TRACES) IS FINITE-STATE RECOGNIZABLE
- scientific article; zbMATH DE number 2187727 (Why is no real title available?)
- Logical definability on infinite traces
- Disjointness, inclusion, and regularity of -rational trace languages (extended abstract)
- On the concatenation of infinite traces
- The poset of infinitary traces
- Bilimites de langages reconnaissables
- On bounded rational trace languages
This page was built for publication: Recognizable and rational languages of finite and infinite traces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035660)