Document Open Access Logo

Better Complexity Bounds for Cost Register Automata

Authors Eric Allender, Andreas Krebs, Pierre McKenzie

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.24.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Eric Allender
Andreas Krebs
Pierre McKenzie

Cite As Get BibTex

Eric Allender, Andreas Krebs, and Pierre McKenzie. Better Complexity Bounds for Cost Register Automata. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.24

Abstract

Cost register automata (CRAs) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers.  Here it is shown that CRAs over the tropical semiring (N U {infinity},\min,+) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P-complete. 
Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC^1 when the semiring is (Z,+,x) or (Gamma^*,max,concat).  This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC^1 versus GapNC^1.

Subject Classification

Keywords
  • computational complexity
  • cost registers

Metrics

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

References

  1. E. Allender and I. Mertz. Complexity of regular functions. Journal of Computer and System Sciences, 2017. To appear; LATA 2015 Special Issue. Earlier version appeared in Proc. 9th International Conference on Language and Automata Theory and Applications (LATA'15), Springer Lecture Notes in Computer Science vol. 8977, pp. 449-460. URL: http://dx.doi.org/10.1016/j.jcss.2016.10.005.
  2. Eric Allender. Arithmetic circuits and counting complexity classes. In J. Krajíček, editor, Complexity of Computations and Proofs, volume 13 of Quaderni di Matematica, pages 33-72. Seconda Università di Napoli, 2004. Google Scholar
  3. Rajeev Alur and Pavol Cerný. Streaming transducers for algorithmic verification of single-pass list-processing programs. In 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL, pages 599-610, 2011. URL: http://dx.doi.org/10.1145/1926385.1926454.
  4. Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions, cost register automata, and generalized min-cost problems. CoRR, abs/1111.0670, 2011. URL: https://arxiv.org/abs/1111.0670.
  5. Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 13-22, 2013. See also the expanded version, [4]. URL: http://dx.doi.org/10.1109/LICS.2013.65.
  6. Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science, (CSL-LICS), page 9. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603151.
  7. Rajeev Alur and Mukund Raghothaman. Decision problems for additive regular functions. In Proc. 40th International Colloquium on Automata, Languages, and Programming (ICALP), number 7966 in Lecture Notes in Computer Science, pages 37-48. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39212-2_7.
  8. D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. Journal of Computer and System Sciences, 38:150-164, 1989. URL: http://dx.doi.org/10.1016/0022-0000(89)90037-8.
  9. D. A. M. Barrington, C.-J. Lu, P. B. Miltersen, and S. Skyum. Searching constant width mazes captures the AC⁰ hierarchy. In Proc. 15th International Symposium on Theoretical Aspects of Computer Science (STACS), number 1373 in Lecture Notes in Computer Science, pages 73-83. Springer, 1998. URL: http://dx.doi.org/10.1007/BFb0028542.
  10. M. Beaudry, P. McKenzie, P. Péladeau, and D. Thérien. Finite monoids: from word to circuit evaluation. SIAM Journal on Computing, 26:138-152, 1997. URL: http://dx.doi.org/10.1137/S0097539793249530.
  11. Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM Journal on Computing, 21(1):54-58, 1992. URL: http://dx.doi.org/10.1137/0221006.
  12. Michaël Cadilhac, Andreas Krebs, and Nutan Limaye. Value automata with filters. CoRR, abs/1510.02393, 2015. URL: http://arxiv.org/abs/1510.02393.
  13. Thomas Colcombet. The theory of stabilisation monoids and regular cost functions. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Proceedings, Part II, pages 139-150, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02930-1_12.
  14. Thomas Colcombet. Regular cost functions, part I: logic and algebra over words. Logical Methods in Computer Science, 9(3), 2013. URL: http://dx.doi.org/10.2168/LMCS-9(3:3)2013.
  15. Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, and Szymon Toruńczyk. Cost functions definable by min/max automata. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 29:1-29:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.29.
  16. Laure Daviaud, Pierre-Alain Reynier, and Jean-Marc Talbot. A generalised twinning property for minimisation of cost register automata. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'16, New York, NY, USA, July 5-8, 2016, pages 857-866, 2016. URL: http://dx.doi.org/10.1145/2933575.2934549.
  17. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer-Verlag New York Inc., 2009. URL: http://dx.doi.org/10.1007/978-3-642-01492-5.
  18. Raymond Greenlaw, H James Hoover, and Walter L Ruzzo. Limits to parallel computation: P-completeness theory. Oxford University Press, 1995. Google Scholar
  19. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65:695-716, 2002. URL: http://dx.doi.org/10.1016/S0022-0000(02)00025-9.
  20. Howard J Karloff and Walter L Ruzzo. The iterated mod problem. Information and Computation, 80(3):193-204, 1989. URL: http://dx.doi.org/10.1016/0890-5401(89)90008-4.
  21. Michal Koucký. Unpublished manuscript, 2003. Google Scholar
  22. Andreas Krebs, Nutan Limaye, and Michael Ludwig. Cost register automata for nested words. In Proc. 22nd International Computing and Combinatorics Conference - (COCOON), number 9797 in LNCS, pages 587-598. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-42634-1_47.
  23. Nancy A Lynch. Straight-line program length as a parameter for complexity analysis. Journal of Computer and System Sciences, 21(3):251-280, 1980. URL: http://dx.doi.org/10.1016/0022-0000(80)90024-0.
  24. Filip Mazowiecki and Cristian Riveros. Maximal partition logic: Towards a logical characterization of copyless cost register automata. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany, pages 144-159, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2015.144.
  25. Filip Mazowiecki and Cristian Riveros. Copyless cost-register automata: Structure, expressiveness, and closure properties. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 53:1-53:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.53.
  26. Jean-Eric Pin. Tropical semirings. Cambridge Univ. Press, Cambridge, 1998. URL: http://dx.doi.org/10.1017/CBO9780511662508.004.
  27. Nicholas Pippenger. On simultaneous resource bounds. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 307-311, 1979. URL: http://dx.doi.org/10.1109/SFCS.1979.29.
  28. H. Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, 1994. URL: http://dx.doi.org/10.1007/978-1-4612-0289-9.
  29. H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York Inc., 1999. URL: http://dx.doi.org/10.1007/978-3-662-03927-4.
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 About DROPS Imprint Privacy Contact