Document Open Access Logo

Weighted Tiling Systems for Graphs: Evaluation Complexity

Authors C. Aiswarya , Paul Gastin

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.34.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

C. Aiswarya
  • Chennai Mathematical Institute, India
  • IRL ReLaX, CNRS, France
Paul Gastin
  • LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, France

Funding

Supported by IRL ReLaX.
  • Aiswarya, C.: Supported by DST Inspire.

Cite AsGet BibTex

C. Aiswarya and Paul Gastin. Weighted Tiling Systems for Graphs: Evaluation Complexity. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.34

Abstract

We consider weighted tiling systems to represent functions from graphs to a commutative semiring such as the Natural semiring or the Tropical semiring. The system labels the nodes of a graph by its states, and checks if the neighbourhood of every node belongs to a set of permissible tiles, and assigns a weight accordingly. The weight of a labeling is the semiring-product of the weights assigned to the nodes, and the weight of the graph is the semiring-sum of the weights of labelings. We show that we can model interesting algorithmic questions using this formalism - like computing the clique number of a graph or computing the permanent of a matrix. The evaluation problem is, given a weighted tiling system and a graph, to compute the weight of the graph. We study the complexity of the evaluation problem and give tight upper and lower bounds for several commutative semirings. Further we provide an efficient evaluation algorithm if the input graph is of bounded tree-width.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantitative automata
Keywords
  • Weighted graph tiling
  • tiling automata
  • Evaluation
  • Complexity
  • Tree-width

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. C. Aiswarya, Paul Gastin, and K. Narayan Kumar. MSO decidability of multi-pushdown systems via split-width. In CONCUR, volume 7454 of Lecture Notes in Computer Science, pages 547-561. Springer, 2012. Google Scholar
  2. C. Aiswarya, Paul Gastin, and K. Narayan Kumar. Verifying communicating multi-pushdown systems via split-width. In (ATVA, volume 8837 of Lecture Notes in Computer Science, pages 1-17, Sidney, Australia, November 2014. Springer. URL: https://doi.org/10.1007/978-3-319-11936-6_1.
  3. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, December 1996. Google Scholar
  4. Benedikt Bollig and Paul Gastin. Non-sequential theory of distributed systems. CoRR, abs/1904.06942, 2019. URL: http://arxiv.org/abs/1904.06942.
  5. Benedikt Bollig and Ingmar Meinecke. Weighted distributed systems and their logics. In International Symposium on Logical Foundations of Computer Science, LFCS 2007, volume 4514 of Lecture Notes in Computer Science, pages 54-68. Springer, 2007. Google Scholar
  6. Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Inf. Comput., 205(5):651-678, 2007. Google Scholar
  7. Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #csp. J. Comput. Syst. Sci., 78(2):681-688, 2012. Google Scholar
  8. Clément Carbonnel and Martin C. Cooper. Tractability in constraint satisfaction problems: a survey. Constraints An Int. J., 21(2):115-144, 2016. Google Scholar
  9. Aiswarya Cyriac. Verification of communicating recursive programs via split-width. (Vérification de programmes récursifs et communicants via split-width). PhD thesis, École normale supérieure de Cachan, France, 2014. URL: https://tel.archives-ouvertes.fr/tel-01015561.
  10. Manfred Droste and Stefan Dück. Weighted automata and logics on graphs. In Mathematical Foundations of Computer Science (MFCS'15), volume 9234 of Lecture Notes in Computer Science, pages 192-204. Springer, 2015. Google Scholar
  11. Manfred Droste and Paul Gastin. The kleene-schützenberger theorem for formal power series in partially commuting variables. Inf. Comput., 153(1):47-80, 1999. Google Scholar
  12. Manfred Droste, Werner Kuich, and Heiko Vogler, editors. Handbook of Weighted Automata. Springer Berlin Heidelberg, 2009. Google Scholar
  13. Manfred Droste, Christian Pech, and Heiko Vogler. A Kleene theorem for weighted tree automata. Theory Comput. Syst., 38(1):1-38, 2005. Google Scholar
  14. Manfred Droste and Heiko Vogler. Weighted tree automata and weighted logics. Theor. Comput. Sci., 366(3):228-247, 2006. Google Scholar
  15. Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. The complexity of weighted boolean #csp. SIAM J. Comput., 38(5):1970-1986, 2009. Google Scholar
  16. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  17. Ina Fichtner. Weighted picture automata and weighted logics. Theory Comput. Syst., 48(1):48-78, 2011. Google Scholar
  18. Paul Gastin and Benjamin Monmege. Adding pebbles to weighted automata: Easy specification & efficient evaluation. Theoretical Computer Science, 534:24-44, May 2014. Google Scholar
  19. Mark W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490-509, 1988. URL: https://doi.org/10.1016/0022-0000(88)90039-6.
  20. Andrei A. Krokhin and Stanislav Zivny. The complexity of valued csps. In Andrei A. Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 233-266. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  21. P. Madhusudan and Gennaro Parlato. The tree width of auxiliary storage. In Thomas Ball and Mooly Sagiv, editors, Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 283-294. ACM, 2011. Google Scholar
  22. Christian Mathissen. Weighted logics for nested words and algebraic formal power series. Logical Methods in Computer Science, 6(1), February 2010. Google Scholar
  23. Ingmar Meinecke. Weighted logics for traces. In Dima Grigoriev, John Harrison, and Edward A. Hirsch, editors, First International Computer Science Symposium in Russia, CSR 2006, volume 3967 of Lecture Notes in Computer Science, pages 235-246. Springer, 2006. Google Scholar
  24. Wolfgang Thomas. On logics, tilings, and automata. In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez Artalejo, editors, Automata, Languages and Programming, pages 441-454, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. Google Scholar
  25. L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, 1979. URL: https://doi.org/10.1016/0304-3975(79)90044-6.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact