Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Canonizable partial order generators
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2012 (English)In: Language and Automata Theory and Applications, Springer Berlin/Heidelberg, 2012, Vol. 7183 LNCS, 445-457 p.Conference paper, Published paper (Refereed)
Abstract [en]

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. In the present work we show that any slice graph can be transitive reduced into a Hasse diagram generator representing the same set of partial orders. This result allow us to establish unknown connections between the true concurrent behavior of bounded p/t-nets and traditional approaches for representing infinite families of partial orders, such as Mazurkiewicz trace languages and Message Sequence Chart (MSC) languages. Going further, we identify the family of weakly saturated slice graphs. The class of partial order languages which can be represented by weakly saturated slice graphs is closed under union, intersection and a suitable notion of complementation (bounded cut-width complementation). The partial order languages in this class also admit canonical representatives in terms of Hasse diagram generators, and have decidable inclusion and emptiness of intersection. Our transitive reduction algorithm plays a fundamental role in these decidability results.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2012. Vol. 7183 LNCS, 445-457 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7183
Keyword [en]
Automata, Canonization, Partial Orders, Complementation, Concurrent behavior, Directed acyclic graphs, Hasse diagrams, Mazurkiewicz traces, Message Sequence Charts, Partial order, Reduction algorithms, Automata theory, Computability and decidability, Directed graphs, Graphic methods
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-99813DOI: 10.1007/978-3-642-28332-1_38Scopus ID: 2-s2.0-84857827986ISBN: 978-364228331-4 (print)OAI: oai:DiVA.org:kth-99813DiVA: diva2:542609
Conference
6th International Conference on Language and Automata Theory and Applications, LATA 2012;A Coruna;5 March 2012 through 9 March 2012
Note
QC 20120802Available from: 2012-08-02 Created: 2012-08-02 Last updated: 2012-08-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
De Oliveira Oliveira, Mateus
By organisation
Theoretical Computer Science, TCS
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 57 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf