RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA

DOI10.1142/S0129054198000192zbMath1319.68133MaRDI QIDQ5248980

Manfred Droste, Dietrich Kuske

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

monadic second-order logicconditional independenceautomaton with concurrency relationsrecognizable languageMazurkiewicz trace

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (4)

Rational elements of summation semirings ⋮ UNAMBIGUOUS SHARED-MEMORY SYSTEMS ⋮ Pomset Languages of Finite Step Transition Systems ⋮ Weighted operator precedence languages

Cites Work

• Recognizable languages in concurrency monoids
• Logical definability on infinite traces
• On the concatenation of infinite traces
• A syntactic congruence for rational \(\omega\)-languages
• Theory of traces
• Star-free trace languages
• Defining conditional independence using collapses
• Representation of computations in concurrent automata by dependence orders
• An extension of Kleene's and Ochmański's theorems to infinite traces
• Deterministic asynchronous automata for infinite traces
• Labelled domains and automata with concurrency
• Weak Second‐Order Arithmetic and Finite Automata
• Concurrent Machines
• CONCURRENT AUTOMATA AND DOMAINS

This page was built for publication: RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA