PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Higher-Order Rank Functions on Directed Graphs

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We introduce a new higher-order rank function with the capability to completely discriminate non-equivalent nodes. We review the partition lattice and rank functions and situate the existing rank functions and higher-order rank functions within the formalization. We propose a new refining operator and a new rank function that are better than the existing ones in some applications. We also show that the entire topology (graph) can be reconstructed from only our higher-order ranks making it possible to compare nodes in different graphs and to update the equivalence of nodes when an edge is added. Finally, we briefly describe the use of our higher-order rank function in analyzing web pages as a possible application in different domains.
Słowa kluczowe
Wydawca
Rocznik
Strony
1--31
Opis fizyczny
Bibliogr. 16 poz., rys., tab.
Twórcy
  • Department of General Systems Studies, University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, Japan
autor
  • Faculty of Economics, Dokkyo University, 1-1, Gakuen-cho, Soka-shi, Saitama, Japan
  • Department of General Systems Studies, University of Tokyo, 3-8-1, Komaba, Meguro-ku, Tokyo, Japan
Bibliografia
  • [1] Milner R. An Algebraic Definition of Simulation Between Programs. In: Proceedings of the 2nd International Joint Conference on Artificial Intelligence. London, UK, September 1-3, 1971. 1971 pp. 481-489. URL http://ijcai.org/Proceedings/71/Papers/044.pdf.
  • [2] Aczel P. Non-well-founded Sets. Center for the Study of Language and Information Publication Lecture Notes. Cambridge University Press, 1988. ISBN: 9780937073223. URL https://books.google.co.jp/books?id=9yaRQgAACAAJ.
  • [3] Horie I, Yamaguchi K, Kashiwabara K. Higher-order rank analysis for web structure. In: HYPERTEXT 2005, Proceedings of the 16th ACM Conference on Hypertext and Hypermedia, September 6-9, 2005, Salzburg, Austria. 2005 pp. 98-106. doi:10.1145/1083356.1083375.
  • [4] Horie I, Yamaguchi K, Kashiwabara K. Pattern detection from web using AFA set theory. In: 9th ACM International Workshop on Web Information and Data Management (WIDM 2007), Lisbon, Portugal, November 9, 2007. 2007 pp. 113-120. doi:10.1145/1316902.1316921.
  • [5] Dovier A, Piazza C, Policriti A. An efficient algorithm for computing bisimulation equivalence. Theor. Comput. Sci., 2004. 311(1-3):221-256. doi:10.1016/S0304-3975(03)00361-X.
  • [6] Paige R, Tarjan RE. Three Partition Refinement Algorithms. SIAM J. Comput., 1987. 16(6):973-989. doi: 10.1137/0216062. URL https://doi.org/10.1137/0216062.
  • [7] Piazza C, Policriti A. Ackermann Encoding, Bisimulations, and OBDDs. TPLP, 2004. 4(5-6):695-718. doi:10.1017/S1471068404002091.
  • [8] Gentilini R, Piazza C, Policriti A. From Bisimulation to Simulation: Coarsest Partition Problems. J. Autom. Reasoning, 2003. 31(1):73-103. doi:10.1023/A:1027328830731.
  • [9] Gentilini R, Piazza C, Policriti A. Rank and simulation: the well-founded case. J. Log. Comput., 2015. 25(6):1331-1349. doi:10.1093/logcom/ext066.
  • [10] Omodeo EG, Policriti A, Tomescu AI. On Sets and Graphs: Perspectives on Logic and Combinatorics. Springer, 2017. ISBN 978-3-319-54981-1. URL https://link.springer.com/book/10.1007%2F978-3-319-54981-1.
  • [11] Hopcroft JE. An N Log N Algorithm for Minimizing States in a Finite Automaton. Technical report, Stanford, CA, USA, 1971.
  • [12] Kanellakis PC, Smolka SA. CCS Expressions, Finite State Processes, and Three Problems of Equivalence. Inf. Comput., 1990. 86(1):43-68. doi:10.1016/0890-5401(90)90025-D.
  • [13] Saha D. An Incremental Bisimulation Algorithm. In: FSTTCS. 2007. doi:10.1007/978-3-540-77050-3_17.
  • [14] Krug S. Don’T Make Me Think!: A Common Sense Approach to Web Usability. Que Corp., Indianapolis, IN, USA, 1st edition, 2000. ISBN: 0789723107.
  • [15] Nielsen J. Designing Web Usability: The Practice of Simplicity. New Riders Publishing, Thousand Oaks, CA, USA, 1999. ISBN: 156205810X.
  • [16] David E, Jon K. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY, USA, 2010. ISBN:0521195330, 9780521195331.
Uwagi
Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-a67d1ec2-b07f-4bf4-ae2e-d7f6c535a883
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.