{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T07:09:57Z","timestamp":1791097797206,"version":"4.1.0"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>The known proofs that the equivalence and containment problems for regular expressions, regular grammars and nondeterministic finite automata are PSPACE-complete [SM] depend upon consideration of highly unambiguous expressions, grammars and automata. Here, we prove that such dependence is inherent.<\/jats:p>\n                  <jats:p>Deterministic polynomial-time algorithms are presented for the equivalence and containment problems for unambiguous regular expressions, unambiguous regular grammars and unambiguous finite automata. The algorithms are then extended to ambiguity bounded by a fixed k. Our algorithms depend upon several elementary observations on the solutions of systems of homogeneous linear difference equations with constant coefficients and their relationship with the number of derivations of strings of a given length n by a regular grammar.<\/jats:p>","DOI":"10.1137\/0214044","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"598-611","source":"Crossref","is-referenced-by-count":96,"title":["On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata"],"prefix":"10.1137","volume":"14","author":[{"given":"R. E.","family":"Stearns","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H. B.","family":"Hunt III","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","volume-title":"The theory of parsing, translation, and compiling. Vol. I: Parsing","author":"Aho Alfred V.","year":"1972"},{"key":"R3","unstructured":"J. A. Brzozowski,  Canonical regular expressions and minimal state graphs for definite events,  Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y.,  1963,  529\u2013561 30:59030116.33605"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90012-6"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744569"},{"key":"R6","volume-title":"Formal languages and their relation to automata","author":"Hopcroft John E.","year":"1969"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90002-3"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80038-4"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(69)80016-2"},{"key":"R10","volume-title":"Counter-free automata","author":"McNaughton Robert","year":"1971"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"A. R. Meyer, M. J. Fischer,  Economy of description by automata, grammars, and formal systems,  Conference Record, Twelfth Annual IEEE Symposium on Switching and Automata Theory, East Lansing, MI,  1971,  144\u2013152, October","DOI":"10.1109\/SWAT.1971.11"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90048-5"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(68)80037-6"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"D. J. Rosenkrantz, H. B. Hunt, III,  Efficient algorithms for structural similarity of grammars,  Proc. 7th ACM Symposium on Principles of Programming Languages, Las Vegas, NV,  1980,  213\u2013219, January","DOI":"10.1145\/567446.567467"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer, A. R. Meyer,  Word problems requiring exponential time: preliminary report,  Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York,  1973,  1\u20139, May 54:65570359.68050","DOI":"10.1145\/800125.804029"},{"key":"R16","volume-title":"Currents in the theory of computing","author":"Thatcher James W.","year":"1973"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Y. Zackstein,  On star-free events,  Conference Record, the Eleventh Annual IEEE Symposium on Switching and Automata Theory,  1970,  76\u201380","DOI":"10.1109\/SWAT.1970.14"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:09Z","timestamp":1787337549000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214044"],"URL":"https:\/\/doi.org\/10.1137\/0214044","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}