{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:37Z","timestamp":1750221217196,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,8,28]],"date-time":"2018-08-28T00:00:00Z","timestamp":1535414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG research project Lo","award":["748\/12-1"],"award-info":[{"award-number":["748\/12-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>\n            The computational complexity of the circuit and expression evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or a multiplicative identity. The following dichotomy is shown: If a finite semiring is such that (i) the multiplicative semigroup is solvable and (ii) it does not contain a subsemiring with an additive identity 0 and a multiplicative identity 1 \u2260 0, then the circuit evaluation problem is in DET \u2286 NC\n            <jats:sup>2<\/jats:sup>\n            , and the expression evaluation problem for the semiring is in TC\n            <jats:sup>0<\/jats:sup>\n            . For all other finite semirings, the circuit evaluation problem is P-complete and the expression evaluation problem is NC\n            <jats:sup>1<\/jats:sup>\n            -complete. As an application, we determine the complexity of intersection non-emptiness problems for given context-free grammars (regular expressions) with a fixed regular language.\n          <\/jats:p>","DOI":"10.1145\/3241375","type":"journal-article","created":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T13:45:11Z","timestamp":1535636711000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Circuits and Expressions over Finite Semirings"],"prefix":"10.1145","volume":"10","author":[{"given":"Moses","family":"Ganardi","sequence":"first","affiliation":[{"name":"University of Siegen, Germany"}]},{"given":"Danny","family":"Hucke","sequence":"additional","affiliation":[{"name":"University of Siegen, Germany"}]},{"given":"Daniel","family":"K\u00f6nig","sequence":"additional","affiliation":[{"name":"University of Siegen, Germany"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[{"name":"University of Siegen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,8,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792540"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00227-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-08-04712-0"},{"volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","key":"e_1_2_1_5_1","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational Complexity - A Modern Approach . Cambridge University Press . Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.027"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63138"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0222-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1035"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793249530"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28409"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90015-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213028"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_2_1_17_1","volume-title":"Cook and Lila Fontes","author":"Stephen","year":"2012","unstructured":"Stephen A. Cook and Lila Fontes . 2012 . Formal theories for linear algebra. Logic. Methods Computer Science 8, 1 (2012). Stephen A. Cook and Lila Fontes. 2012. Formal theories for linear algebra. Logic. Methods Computer Science 8, 1 (2012)."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","volume":"14","author":"Elberfeld M.","unstructured":"M. Elberfeld , A. Jakoby , and T. Tantau . 2012. Algorithmic meta theorems for circuit classes of constant and logarithmic depth . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201912) , Vol. 14 . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 66--77. M. Elberfeld, A. Jakoby, and T. Tantau. 2012. Algorithmic meta theorems for circuit classes of constant and logarithmic depth. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201912), Vol. 14. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 66--77."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1485"},{"key":"e_1_2_1_20_1","volume-title":"A universal tree balancing theorem. CoRR abs\/1704.08705","author":"Ganardi Moses","year":"2017","unstructured":"Moses Ganardi and Markus Lohrey . 2017. A universal tree balancing theorem. CoRR abs\/1704.08705 ( 2017 ). http:\/\/arxiv.org\/abs\/1704.08705 Moses Ganardi and Markus Lohrey. 2017. A universal tree balancing theorem. CoRR abs\/1704.08705 (2017). http:\/\/arxiv.org\/abs\/1704.08705"},{"volume-title":"Semirings and Their Applications","author":"Golan Jonathan S.","key":"e_1_2_1_21_1","unstructured":"Jonathan S. Golan . 1999. Semirings and Their Applications . Springer . Jonathan S. Golan. 1999. Semirings and Their Applications. Springer."},{"key":"e_1_2_1_22_1","volume-title":"Ruzzo","author":"Greenlaw Raymond","year":"1995","unstructured":"Raymond Greenlaw , H. James Hoover , and Walter L . Ruzzo . 1995 . Limits to Parallel Computation : P-Completeness Theory. Oxford University Press . Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo. 1995. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/322358.322373"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90068-2"},{"key":"e_1_2_1_25_1","volume-title":"Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica","author":"K\u00f6nig Daniel","year":"2017","unstructured":"Daniel K\u00f6nig and Markus Lohrey . 2017. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica ( 2017 ). Daniel K\u00f6nig and Markus Lohrey. 2017. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica (2017)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/111662.111680"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/990518.990519"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/647200.718725"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0229-6"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217044"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281724"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1673"},{"volume-title":"The q-theory of Finite Semigroups","author":"Rhodes John","key":"e_1_2_1_33_1","unstructured":"John Rhodes and Benjamin Steinberg . 2008. The q-theory of Finite Semigroups . Springer . John Rhodes and Benjamin Steinberg. 2008. The q-theory of Finite Semigroups. Springer."},{"key":"e_1_2_1_34_1","series-title":"Lecture Notes in Computer Science","volume-title":"Vyalyi","author":"Rubtsov Alexander A.","year":"2015","unstructured":"Alexander A. Rubtsov and Mikhail N . Vyalyi . 2015 . Regular realizability problems and context-free languages. In Proceedings of the 17th International Workshop on Descriptional Complexity of Formal Systems (DCFS\u201915), Lecture Notes in Computer Science , Vol. 9118 . Springer , 256--267. Alexander A. Rubtsov and Mikhail N. Vyalyi. 2015. Regular realizability problems and context-free languages. In Proceedings of the 17th International Workshop on Descriptional Complexity of Formal Systems (DCFS\u201915), Lecture Notes in Computer Science, Vol. 9118. Springer, 256--267."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/646589.697341"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.08.017"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 4th Workshop on Computer Science Logic (CSL\u201990)","volume":"533","author":"Vollmer Heribert","year":"1990","unstructured":"Heribert Vollmer . 1990 . The gap-language-technique revisited . In Proceedings of the 4th Workshop on Computer Science Logic (CSL\u201990) , Lecture Notes in Computer Science , Vol. 533 . Springer, 389--399. Heribert Vollmer. 1990. The gap-language-technique revisited. In Proceedings of the 4th Workshop on Computer Science Logic (CSL\u201990), Lecture Notes in Computer Science, Vol. 533. Springer, 389--399."},{"volume-title":"Introduction to Circuit Complexity","author":"Vollmer Heribert","key":"e_1_2_1_40_1","unstructured":"Heribert Vollmer . 1999. Introduction to Circuit Complexity . Springer . Heribert Vollmer. 1999. Introduction to Circuit Complexity. Springer."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3241375","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3241375","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:53Z","timestamp":1750210793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3241375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,28]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3241375"],"URL":"https:\/\/doi.org\/10.1145\/3241375","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,8,28]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}