×

On the complexity of regular-grammars with integer attributes. (English) Zbl 1218.68093

An attribute grammar is a quadruple \(\mathit{AG} = (G, \mathit{Attr}, \mathit{Func}, \mathit{Pred})\) where \(G\) is a regular (context-free) grammar; \(\mathit{Attr}\) is a set of integer attributes associated with the nonterminals of \(G\); \(\mathit{Func}\) is a set of functions associated with the production rules of \(G\), assigning values to attributes by means of arithmetic expressions over the set \(S\) of operators of absolute value, addition, subtraction, integer division, modulo reduction, multiplication; \(\mathit{Pred}\) is a set of predicates, associated with the production rules of \(G\), cheking values of attributes. A predicate is a Boolean combination of comparison predicates of the form \(E_1\odot E_2\), where \(\odot\) is one of the signs in \(\{<,\leq,=,>,\geq,\neq\}\), and \(E_1,E_2\) are arithmetic expressions over \(S\). The language \(L(AG)\) generated by \(AG\) is the set of all strings derived by some valid parse tree for \(AG\).
It is shown that PARSE is tractable for the following classes of integer attribute grammars: (i) deterministic regular strict grammars with arithmetic expressions over \(S_1\) (which is \(S\) without multiplication); (ii) general (possibly ambiguous) regular strict grammars with arithmetic expressions over \(S_1\); (iii) deterministic regular grammars with arithmetic expressions over \(S_1\) without the strict-restriction; (iv) deterministic regular strict grammars with arithmetic operators from \(S\). In particular, PARSE is L-complete in case (i); NL-complete in case (ii); P-complete in cases (iii) and (iv).
The authors employ \(AG\) as a system for ontology-based information extraction used in real-word applications.

MSC:

68Q42 Grammars and rewriting systems
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata

Software:

GAG; CONSTRUCTOR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Alblas, H.; Melichar, B., SAGA’91: Proceedings of the International Summer School on Attribute Grammars, Applications and Systems. SAGA’91: Proceedings of the International Summer School on Attribute Grammars, Applications and Systems, Prague, Czechoslovakia, June 4-13, 1991. SAGA’91: Proceedings of the International Summer School on Attribute Grammars, Applications and Systems. SAGA’91: Proceedings of the International Summer School on Attribute Grammars, Applications and Systems, Prague, Czechoslovakia, June 4-13, 1991, Lecture Notes in Comput. Sci., vol. 545 (1991), Springer: Springer Berlin, Heidelberg) · Zbl 0875.00087
[2] Alexin, Z.; Gyimóthy, T.; Horváth, T.; Fábricz, K., Attribute grammar specification for a natural language understanding interface, (Proceedings of the International Conference WAGA on Attribute Grammars and Their Applications. Proceedings of the International Conference WAGA on Attribute Grammars and Their Applications, Paris, France, September 19-21, 1990. Proceedings of the International Conference WAGA on Attribute Grammars and Their Applications. Proceedings of the International Conference WAGA on Attribute Grammars and Their Applications, Paris, France, September 19-21, 1990, Lecture Notes in Comput. Sci., vol. 461 (1990), Springer: Springer Berlin, Heidelberg), 313-326 · Zbl 0705.68084
[3] Allender, E.; Loui, M. C.; Regan, K. W., Complexity Classes (1998), CRC Press, pp. 27.1-27.23
[4] Barrington, D. A., Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^1\), (STOC’86 - Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing. STOC’86 - Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley, CA, United States, May 28-30, 1986 (1986), ACM: ACM New York, NY, USA), 1-5
[5] Borodin, A., On relating time and space to size and depth, SIAM J. Comput., 6, 4, 733-744 (1977) · Zbl 0366.68039
[6] Brandenburg, F.-J., On one-way auxiliary pushdown automata, (Proceedings of the 3rd GI Conference Darmstadt on Theoretical Computer Science, March 28-30, 1977. Proceedings of the 3rd GI Conference Darmstadt on Theoretical Computer Science, March 28-30, 1977, Lecture Notes in Comput. Sci., vol. 48 (1977), Springer: Springer Berlin, Heidelberg), 132-144 · Zbl 0359.68055
[7] Chiu, A.; Davida, G.; Litow, B., Division in logspace-uniform \(NC^1\), RAIRO Theor. Inform. Appl., 35, 3, 259-275 (2001) · Zbl 1014.68062
[8] (Deransart, P.; Jourdan, M., WAGA’90: Proceedings of the International Conference on Attribute Grammars and Their Applications. WAGA’90: Proceedings of the International Conference on Attribute Grammars and Their Applications, Paris, France, September 19-21, 1990. WAGA’90: Proceedings of the International Conference on Attribute Grammars and Their Applications. WAGA’90: Proceedings of the International Conference on Attribute Grammars and Their Applications, Paris, France, September 19-21, 1990, Lecture Notes in Comput. Sci., vol. 461 (1990), Springer: Springer Berlin, Heidelberg)
[9] Deransart, P.; Jourdan, M.; Lorho, B., Attribute Grammars - Definitions, Systems and Bibliography, Lecture Notes in Comput. Sci., vol. 323 (1988), Springer: Springer Berlin, Heidelberg · Zbl 0647.68073
[10] Deransart, P.; Maluszynski, J., Relating logic programs and attribute grammars, J. Log. Program., 2, 2, 119-155 (1985) · Zbl 0586.68073
[11] Deransart, P.; Maluszynski, J., A Grammatical View of Logic Programming (1993), MIT Press: MIT Press Cambridge, MA, USA · Zbl 0849.68010
[12] Efremidis, S.; Papadimitriou, C. H.; Sideri, M., Complexity characterizations of attribute grammar languages, Inform. and Comput., 78, 3, 178-186 (1988) · Zbl 0672.68035
[13] L. Eikvil, Information Extraction from World Wide Web - A Survey, Tech. Rep. 945, Norwegian Computing Center, 1999.; L. Eikvil, Information Extraction from World Wide Web - A Survey, Tech. Rep. 945, Norwegian Computing Center, 1999.
[14] I. Fang, FOLDS - A declarative semantic formal language definition system, Tech. Rep. STAN-CS-72-239, Computer Science Department, Stanford University, Stanford, Calif., 1972.; I. Fang, FOLDS - A declarative semantic formal language definition system, Tech. Rep. STAN-CS-72-239, Computer Science Department, Stanford University, Stanford, Calif., 1972.
[15] Farrow, R., LINGUIST-86: Yet another translator writing system based on attribute grammars, (SIGPLAN’82 - Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction. SIGPLAN’82 - Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, Boston, MA, United States, June 23-25, 1982 (1982), ACM: ACM New York, NY, USA), 160-171
[16] Feldman, R.; Aumann, Y.; Finkelstein-Landau, M.; Hurvitz, E.; Regev, Y.; Yaroshevich, A., A comparative study of information extraction strategies, (Proceedings of the Third International Conference, CICLing 2002 on Computational Linguistics and Intelligent Text Processing. Proceedings of the Third International Conference, CICLing 2002 on Computational Linguistics and Intelligent Text Processing, Mexico City, Mexico, February 17-23, 2002. Proceedings of the Third International Conference, CICLing 2002 on Computational Linguistics and Intelligent Text Processing. Proceedings of the Third International Conference, CICLing 2002 on Computational Linguistics and Intelligent Text Processing, Mexico City, Mexico, February 17-23, 2002, Lecture Notes in Comput. Sci., vol. 2276 (2002), Springer: Springer Berlin, Heidelberg), 21-34
[17] Feldman, R.; Rosenfeld, B.; Fresko, M., TEG—a hybrid approach to information extraction, Knowl. Inf. Syst., 9, 1, 1-18 (2006)
[18] Furer, M., Faster integer multiplication, SIAM J. Comput., 39, 3, 979-1005 (2009) · Zbl 1192.68926
[19] Ginsburg, S.; Greibach, S. A., Deterministic context free languages, (SWCT’65 - Conference Record of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965 (1965), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA), 203-220 · Zbl 0145.00802
[20] Greibach, S. A., The hardest context-free language, SIAM J. Comput., 2, 4, 304-310 (1973) · Zbl 0278.68073
[21] Hartmanis, J.; Simon, J., On the power of multiplication in random access machines, (SWAT’74 - Proceedings of the 15th IEEE Annual Symposium on Switching and Automata Theory. SWAT’74 - Proceedings of the 15th IEEE Annual Symposium on Switching and Automata Theory, University of New Orleans, USA, 14-16 October, 1974 (1974), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA), 13-23
[22] Hesse, W.; Allender, E.; Barrington, D. A.M., Uniform constant-depth threshold circuits for division and iterated multiplication, J. Comput. Syst. Sci., 65, 4, 695-716 (2002) · Zbl 1059.68044
[23] Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation, 3/E (2007), Addison-Wesley
[24] Ibarra, O. H.; Jiang, T.; Ravikumar, B.; Chang, J. H., On some languages in \(NC^1\) (Extended abstract), (VLSI Algorithms and Architectures (AWOC’88) - Proceedings of the 3rd Aegean Workshop on Computing. VLSI Algorithms and Architectures (AWOC’88) - Proceedings of the 3rd Aegean Workshop on Computing, Corfu, Greece, June 28-July 1, 1988. VLSI Algorithms and Architectures (AWOC’88) - Proceedings of the 3rd Aegean Workshop on Computing. VLSI Algorithms and Architectures (AWOC’88) - Proceedings of the 3rd Aegean Workshop on Computing, Corfu, Greece, June 28-July 1, 1988, Lecture Notes in Comput. Sci., vol. 319 (1988), Springer: Springer Berlin, Heidelberg), 64-73
[25] Kastens, U.; Hutt, B.; Zimmermann, E., GAG: A Practical Compiler Generator, Lecture Notes in Comput. Sci., vol. 141 (1982), Springer: Springer Berlin, Heidelberg · Zbl 0492.68004
[26] Kennedy, K.; Warren, S. K., Automatic generation of efficient evaluators for attribute grammars, (POPL’76 - Proceedings of the 3rd ACM SIGACT-SIGPLAN Symposium on Principles on Programming Languages. POPL’76 - Proceedings of the 3rd ACM SIGACT-SIGPLAN Symposium on Principles on Programming Languages, Atlanta, Georgia, January 19-21, 1976 (1976), ACM: ACM New York, NY, USA), 32-49
[27] Knuth, D. E., Semantics of context-free languages, Theory Comput. Syst., 2, 2, 127-145 (1968) · Zbl 0169.01401
[28] Knuth, D. E., The genesis of attribute grammars, (WAGA’90 - Proceedings of the International Conference on Attribute Grammars and Their Applications. WAGA’90 - Proceedings of the International Conference on Attribute Grammars and Their Applications, Paris, France, September 19-21, 1990. WAGA’90 - Proceedings of the International Conference on Attribute Grammars and Their Applications. WAGA’90 - Proceedings of the International Conference on Attribute Grammars and Their Applications, Paris, France, September 19-21, 1990, Lecture Notes in Comput. Sci., vol. 461 (1990), Springer: Springer Berlin, Heidelberg), 1-12
[29] Koch, C.; Scherzinger, S., Attribute grammars for scalable query processing on XML streams, VLDB J., 16, 3, 317-342 (2007)
[30] Koskimies, K.; Nurmi, O.; Pakki, J., The design of a language processor generator, Software: Practice and Experience, 18, 2, 107-135 (1988)
[31] Kuhlins, S.; Tredwell, R., Toolkits for generating wrappers - A survey of software toolkits for automated data extraction from web sites, (Objects, Components, Architectures, Services, and Applications for a Networked World - International Conference NetObjectDays, NODe 2002 Erfurt, Revised Papers. Objects, Components, Architectures, Services, and Applications for a Networked World - International Conference NetObjectDays, NODe 2002 Erfurt, Revised Papers, Germany, October 7-10, 2002. Objects, Components, Architectures, Services, and Applications for a Networked World - International Conference NetObjectDays, NODe 2002 Erfurt, Revised Papers. Objects, Components, Architectures, Services, and Applications for a Networked World - International Conference NetObjectDays, NODe 2002 Erfurt, Revised Papers, Germany, October 7-10, 2002, Lecture Notes in Comput. Sci., vol. 2591 (2003), Springer: Springer Berlin, Heidelberg), 184-198 · Zbl 1021.68694
[32] Kuroda, S.-Y., Classes of languages and linear-bounded automata, Inform. and Control, 7, 2, 207-223 (1964) · Zbl 0199.04002
[33] Laender, A. H.F.; Ribeiro-Neto, B. A.; da Silva, A. S.; Teixeira, J. S., A brief survey of web data extraction tools, SIGMOD Rec., 31, 2, 84-93 (2002)
[34] Lewis, H. R.; Papadimitriou, C. H., Elements of the Theory of Computation (1997), Prentice Hall PTR: Prentice Hall PTR Upper Saddle River, NJ, USA
[35] Lewis, P. M.; Rosenkrantz, D. J.; Stearns, R. E., Attributed translations, J. Comput. System Sci., 9, 3, 279-307 (1974) · Zbl 0308.68073
[36] Lewis, P. M.; Stearns, R. E.; Hartmanis, J., Memory bounds for recognition of context-free and context-sensitive languages, (SWCT’65 - Conference Record of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965 (1965), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA), 191-202 · Zbl 0272.68054
[37] Løvborg, S. J., Declarative Programming and Natural Language (2007)
[38] Muchnik, A. A., One application of real-valued interpretation of formal power series, Theoret. Comput. Sci., 290, 3, 1931-1946 (2003) · Zbl 1044.68080
[39] Neven, F., Extensions of attribute grammars for structured document queries, (Research Issues in Structured and Semistructured Database Programming (DBPL’99) - Revised Papers of the 7th International Workshop on Database Programming Languages. Research Issues in Structured and Semistructured Database Programming (DBPL’99) - Revised Papers of the 7th International Workshop on Database Programming Languages, Kinloch Rannoch, UK, September 1-3, 1999. Research Issues in Structured and Semistructured Database Programming (DBPL’99) - Revised Papers of the 7th International Workshop on Database Programming Languages. Research Issues in Structured and Semistructured Database Programming (DBPL’99) - Revised Papers of the 7th International Workshop on Database Programming Languages, Kinloch Rannoch, UK, September 1-3, 1999, Lecture Notes in Comput. Sci., vol. 1949 (2000), Springer: Springer Berlin, Heidelberg), 99-117 · Zbl 1044.68045
[40] Neven, F., Attribute grammars for unranked trees as a query language for structured documents, J. Comput. System Sci., 70, 2, 221-257 (2005) · Zbl 1101.68636
[41] Neven, F.; Van Den Bussche, J., Expressiveness of structured document query languages based on attribute grammars, J. ACM, 49, 1, 56-100 (2002) · Zbl 1323.68253
[42] Ostrand, T. J.; Paull, M. C.; Weyuker, E. J., Parsing regular grammars with finite lookahead, Acta Inform., 16, 2, 125-138 (1981) · Zbl 0452.68089
[43] Paakki, J., Attribute grammar paradigms—a high-level methodology in language implementation, ACM Comput. Surv., 27, 2, 196-255 (1995)
[44] Papadimitriou, C. M., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049
[45] Papakonstantinou, Y.; Vianu, V., DTD inference for views of XML data, (PODS’00 - Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. PODS’00 - Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Dallas, TX, United States, May 14-19, 2000 (2000), ACM: ACM New York, NY, USA), 35-46
[46] Rabin, M. O., Two-way finite automata, (Proceedings of the Summer Institute of Symbolic Logic, Cornell University, 1957 (1960), Communications Research Division, Institute for Defense Analyses: Communications Research Division, Institute for Defense Analyses Princeton, NJ), 366-369 · Zbl 0148.01003
[47] Ridjanovic, D.; Brodie, M. L., Defining database dynamics with attribute grammars, Inform. Process. Lett., 14, 3, 132-138 (1982)
[48] Ruffolo, M.; Manna, M., \(Hı\) L \(ε\) X: A system for semantic information extraction from web documents, (Enterprise Information Systems, 8th International Conference, ICEIS 2006, Revised Selected Papers. Enterprise Information Systems, 8th International Conference, ICEIS 2006, Revised Selected Papers, Paphos, Cyprus, May 23-27, 2006. Enterprise Information Systems, 8th International Conference, ICEIS 2006, Revised Selected Papers. Enterprise Information Systems, 8th International Conference, ICEIS 2006, Revised Selected Papers, Paphos, Cyprus, May 23-27, 2006, Lecture Notes in Business Information Processing, vol. 3 (2008), Springer: Springer Berlin, Heidelberg), 194-209
[49] Ruffolo, M.; Manna, M.; Gallucci, L.; Leone, N.; Saccà, D., A logic-based tool for semantic information extraction, (Proceedings of the 10th European Conference, JELIA 2006 on Logics in Artificial Intelligence. Proceedings of the 10th European Conference, JELIA 2006 on Logics in Artificial Intelligence, Liverpool, UK, September 13-15, 2006. Proceedings of the 10th European Conference, JELIA 2006 on Logics in Artificial Intelligence. Proceedings of the 10th European Conference, JELIA 2006 on Logics in Artificial Intelligence, Liverpool, UK, September 13-15, 2006, Lecture Notes in Comput. Sci., vol. 4160 (2006), Springer: Springer Berlin, Heidelberg), 506-510
[50] Ruzzo, W. L., On uniform circuit complexity, (FOCS’79 - Proceedings of the 20th IEEE Annual Symposium on Foundations of Computer Science, October 29-31, 1979 (1979), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA), 312-318
[51] Ruzzo, W. L., Tree-size bounded alternation, J. Comput. Syst. Sci., 21, 2, 218-235 (1980) · Zbl 0445.68034
[52] Schönhage, A.; Strassen, V., Schnelle Multiplikation großer Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007
[53] Shepherdson, J. C., The reduction of two-way automata to one-way automata, IBM J. Research and Development, 3, 2, 198-200 (1959) · Zbl 0158.25601
[54] Simovici, D. A.; Tenney, R., Theory of Formal Languages with Applications (1999), World Scientific: World Scientific Singapore · Zbl 0943.68099
[55] Stenback, J.; Heninger, A., Document Object Model (DOM) Level 3 Load and Save Specification, W3C Recommendation (April 2004)
[56] Sudborough, I. H., On the tape complexity of deterministic context-free languages, J. ACM, 25, 3, 405-414 (1978) · Zbl 0379.68054
[57] Trahanias, P.; Skordalakis, E., Syntactic pattern recognition of the ECG, IEEE Trans. Pattern Analysis and Machine Intelligence, 12, 7, 648-657 (1990)
[58] Wegener, I., The Complexity of Boolean Functions (1987), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, NY, USA · Zbl 0623.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.