Computer Science – Formal Languages and Automata Theory
Scientific paper
2010-09-27
Computer Science
Formal Languages and Automata Theory
Full Version. 30 pages. 7 Figures
Scientific paper
In a previous work we introduced slice graphs as a way to specify both infinite languages of directed acyclic graphs (DAGs) and infinite languages of partial orders. Therein we focused on the study of Hasse diagram generators, i.e., slice graphs that generate only transitive reduced DAGs, and showed that they could be used to solve several problems related to the partial order behavior of p/t-nets. In the present work we show that both slice graphs and Hasse diagram generators are worth studying on their own. First, we prove that any slice graph SG can be effectively transformed into a Hasse diagram generator HG representing the same set of partial orders. Thus from an algorithmic standpoint we introduce a method of transitive reducing infinite families of DAGs specified by slice graphs. Second, we identify the class of saturated slice graphs. By using our transitive reduction algorithm, we prove that the class of partial order languages representable by saturated slice graphs is closed under union, intersection and even under a suitable notion of complementation (cut-width complementation). Furthermore partial order languages belonging to this class can be tested for inclusion and admit canonical representatives in terms of Hasse diagram generators. As an application of our results, we give stronger forms of some results in our previous work, and establish some unknown connections between the partial order behavior of $p/t$-nets and other well known formalisms for the specification of infinite families of partial orders, such as Mazurkiewicz trace languages and message sequence chart (MSC) languages.
No associations
LandOfFree
Canonizable Partial Order Generators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Canonizable Partial Order Generators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Canonizable Partial Order Generators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-518548