Characterizations of the decidability of some problems for regular trace languages

DOI10.1007/BF02088289zbMath0679.68132WikidataQ57402290 ScholiaQ57402290MaRDI QIDQ4729376

Hendrik Jan Hoogeboom, Ijsbrand Jan Aalbersberg

Publication date: 1989

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

decidabilityequivalence problemdisjointness problemregular trace languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

Weak equivalence of higher-dimensional automata, On the synchronization of semi-traces, Intersection problem for Droms RAAGs, Solving trace equations using lexicographical normal forms, The emptiness problem for valence automata over graph monoids, Decidability and complexity for quiescent consistency and its variations, The code problem for traces -- improving the boundaries, Logical definability of some rational trace languages, RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS, Knapsack in graph groups, WORD EQUATIONS OVER GRAPH PRODUCTS, Solving word equations modulo partial commutations, Fixed points of endomorphisms of trace monoids., Probabilistic estimation of the number of prefixes of a trace, On some decision problems for trace codings, Bounded Context Switching for Valence Systems, The word problem for one-relation monoids: a survey, The submonoid and rational subset membership problems for graph groups., Rational relations and rational series, Automated Synthesis of Application-Layer Connectors from Automata-Based Specifications, Model-checking of correctness conditions for concurrent objects, On the support of graph Lie algebras

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Partial commutations and faithful rational transductions
• Traces, dependency graphs and DNLC grammars
• On the decidability of some problems about rational subsets of free partially commutative monoids
• Theory of traces
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• Trace languages defined by regular string languages
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• A Note on "The Comparability Graph of a Tree"
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item