Membership problems for regular and context-free trace languages

DOI10.1016/0890-5401(89)90051-5zbMath0682.68040OpenAlexW1965367600WikidataQ57518713 ScholiaQ57518713MaRDI QIDQ1824384

Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90051-5

zbMATH Keywords

concurrent systemsNP-completefree partially commutative monoidTrace languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Theory of operating systems (68N25)

Related Items

Asynchronous automata versus asynchronous cellular automata, Clique polynomials have a unique root of smallest modulus, Theory of traces, Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata, Parsing by matrix multiplication generalized to Boolean grammars, Probabilistic asynchronous automata, A survey on automata with translucent letters, Knapsack in graph groups, Preface, Linear automata with translucent letters and linear context-free trace languages, Probabilistic estimation of the number of prefixes of a trace, Closure properties of knapsack semilinear groups, Star-free trace languages, Quantum finite automata: advances on Bertoni's ideas, Realizability and verification of MSC graphs, Efficient recognition of trace languages defined by repeat-until loops, On Restarting Automata with Window Size One, An Automata-Theoretical Characterization of Context-Free Trace Languages, The lattices of prefixes and overlaps of traces, CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store, Confluence problems for trace rewriting systems

Cites Work

• 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
• Modeling concurrency with partial orders
• Petri nets, event structures and domains. I
• General context-free recognition in less than cubic time
• Combinatorial problems of commutation and rearrangements
• A decomposition theorem for partially ordered sets
• Notes on finite asynchronous automata
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• On Context-Free Languages