Sequential Constraint Grammar (SCG) (Karlsson, 1990) and its extensions have lacked clear connections to formal language theory. The purpose of this article is to lay a foundation for these connections by simplifying the definition of strings processed by the grammar and by showing that Nonmonotonic SCG is undecidable and that derivations similar to the Generative Phonology exist. The current investigations propose resource bounds that restrict the generative power of SCG to a subset of context sensitive languages and present a strong finite-state condition for grammars as wholes. We show that a grammar is equivalent to a finite-state transducer if it is implemented with a Turing machine that runs in o(nlogn) time. This condition opens new finite-state hypotheses and avenues for deeper analysis of SCG instances in the way inspired by Finite-State Phonology.
Kazimierz Ajdukiewicz. 1935. Die syntaktische konnexit ¨at. In Storrs McCall, editor, Polish Logic 1920-1939, page 207231. Oxford University Press, Oxford. Translated from Studia Philosophica, 1, 1-27.
Yehoshua Bar-Hillel. 1953. A quasi-arithmetical notation for syntactic description. Language, 29:4758.
J. R. Büchi. 1960. Weak second-order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 6:66–92.
Jean-Pierre Chanod and Pasi Tapanainen. 1995. A lexical interface for finite-state syntax. MLTT technical report, Rank Xerox Research Centre, Grenoble Laboratory, Grenoble, France, February 9.
Noam Chomsky and Morris Halle. 1968. The Sound Pattern of English. Harper & Row, New York.
Noam Chomsky. 1965. Aspects of the Theory of Syntax. MIT Press, Cambridge, Massachusetts.
M. B. Clowes. 1971. On seeing things. Artificiul Intelligence, 2:79–116.
Tino Didriksen, 2017. Constraint Grammar Manual: 3rd version of the CG formalism variant. Grammar-Soft ApS, Denmark.
Jason Eisner and Noah A. Smith. 2005. Parsing with soft and hard constraints on dependency length. In Proceedings of the Ninth International Workshop on Parsing Technology, pages 30–41, Vancouver, British Columbia, October. Association for Computational Linguistics.
Calvin C. Elgot. 1961. Decision problems of finite automata design and related arithmetics. Transactions of the American Mathematical Society, 98(1):21–51.
David Gajser. 2015. Verifying Time Complexity of Turing Machines. Ph.D. thesis, University of Ljubljana, Department of Mathematics, Ljubljana, Slovenia.
Sheila Greibach. 1973. The hardest context-free language. SIAM Journal on Computing, 2(4):304–310.
Maurice Gross. 1997. The construction of local grammars. In Emmanuel Roche and Yves Schabes, editors, Finite-State Language Processing, chapter 11, pages 329–354. A Bradford Book, the MIT Press, Cambridge, MA, USA.
Juri Hartmanis. 1968. Computational complexity of one-tape Turing machine computations. J. ACM, 15(2):325–339, April.
Frederick C. Hennie. 1965. One-tape, off-line Turing machine computations. Information and Control, 8(6):553–578.
D. A. Huffman. 1971. Impossible objects as nonsense sentences. In B. Meltzer and D. Michie, editors, Machine Intelligence, volume 6, pages 295–323. Edinburgh University Press, Edinburgh, Scotland.
Måns Hulden. 2009. Finite-State Machine Construction Methods and Algorithms for Phonology and Morphology. Ph.D. thesis, Department of Linguistics, The University of Arizona.
Mans Hulden. 2011. Constraint Grammar parsing with left and right sequential finite transducers. In Proceedings of the 9th International Workshop on Finite State Methods and Natural Language Processing (FSMNLP 2011), pages 39–47, Blois, France, July. Association for Computational Linguistics.
C. Douglas Johnson. 1972. Formal Aspects of Phonological Description. Number 3 in Monographs on linguistic analysis. Mouton, The Hague.
Ronald M. Kaplan and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20(3):331–378, September.
Fred Karlsson. 1990. Constraint Grammar as a framework for parsing unrestricted text. In H. Karlgren, editor, Proceedings of the 13th International Conference of Computational Linguistics, volume 3, pages 168–173, Helsinki.
Lauri Karttunen. 1994. Constructing lexical transducers. In 15th COLING 1994, Proceedings of the Conference, volume 1, pages 406–411, Kyoto, Japan.
K. Kobayashi. 1985. On the structure of one-tape nondeterministic Turing machine time hierarchy. Theoretical Computer Science, 40(2–3):175–193.
Kimmo Koskenniemi. 1990. Finite-state parsing and disambiguation. In Hans Karlgren, editor, 13th COLING 1990, Proceedings of the Conference, volume 2, pages 229–232, Helsinki, Finland, August.
Sige-Yuki Kuroda. 1964. Classes of languages and linear-bounded automata. Information and Control, 7(2):207–223.
Torbjörn Lager and Joakim Nivre. 2001. Part of speech tagging from a logical point of view. In P. de Groote, G. Morrill, and C. Retor´e, editors, Logical Aspects of Computational Linguistics, volume 2099 of Lecture Notes in Artificial Intelligence, pages 212–227. Springer-Verlag.
Joachim Lambek. 1958. The mathematics of sentence structure. American Mathematical Monthly, 65:154–170.
Nikolaj Lindberg and Martin Eineborg. 1998. Learning Constraint Grammar-style disambiguation rules using Inductive Logic Programming. In 36th ACL 1998, 17th COLING 1998, Proceedings of the Conference, Montréal, Quebec, Canada, August 10-14.
Inari Listenmaa. 2016. Analysing Constraint Grammar with SAT. Licentiate thesis, Chalmers University of Technology and University of Gothenburg, Gothenburg, Sweden.
Hiroshi Maruyama. 1990. Structural disambiguation with contraint propagation. In 28th ACL 1989, Proceedings of the Conference, pages 31–38, Pittsburgh, Pennsylvania, June 6-9.
John Myhill. 1960. Linear bounded automata. Wadd technical note, Wright Patterson AFB, Wright Air Development Division, Ohio, June.
Alexander Okhotin. 2013. Inverse homomorphic characterizations of Conjunctive and Boolean Grammars. Technical Report 1080, Turku Centre for Computer Science, Turku.
Janne Peltonen. 2011. Finite state Constraint Grammar parser. In Proceedings of the NODALIDA 2011 workshop Constraint Grammar Applications, May 11, 2011, volume 14 of NEALT Proceedings Series, Riga, Latvia.
P. S. Peters and R.W. Ritchie. 1973. On the generative power of transformational grammars. Information Sciences, 6:49–83.
Amir Pnueli. 1977. The temporal logic of programs. In Proceedings of the IEEE 18th Annual Symposium on Foundations Computer Science, pages 46–57, New York.
Daniel Pruša. 2014. Weight-reducing Hennie machines and their descriptional complexity. In Language and Automata Theory and Applications: 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings, pages 553–564, Cham. Springer International Publishing.
Michael O. Rabin. 1963. Real time computation. Israel Journal of Mathematics, 1(4):203–211.
Eric Sven Ristad. 1990. Computational structure of generative phonology and its relation to language comprehension. In Proceedings of the 28th Annual Meeting on Association for Computational Linguistics, ACL ’90, pages 235–242, Pittsburgh, Pennsylvania.
Kai Salomaa and Sheng Yu. 2000. Alternating finite automata and star-free languages. Theoretical Computer Science, 234:167–176.
Wojciech Skut, Stefan Ulrich, and Kathrine Hammervold. 2004. A bimachine compiler for ranked tagging rules. In Proc. 20th Int’l Conf. on Computational Linguistics, COLING ’04, Stroudsburg, PA, USA.
Kohtaro Tadaki, Tomoyuki Yamakami, and Jack C. H. Lin. 2010. Theory of one-tape linear-time Turing machines. Theoretical Computer Science, 411(1):22–43.
Pasi Tapanainen. 1996. The Constraint Grammar Parser CG-2, volume 27 of Publications. Department of General Linguistics, University of Helsinki. Pasi Tapanainen. 1999. Parsing in two frameworks: finite-state and functional dependency grammar. Ph.D. thesis, University of Helsinki, Finland, 1 December.
B. A. Trakhtenbrot. 1961. Finite automata and logic of monadic predicates. Doklady Akademii Nauk SSSR, 140:326–329. In Russian.
Boris A. Trakhtenbrot. 1964. Turing computations with logarithmic delay (in Russian). Albegra i Logica, pages 33–34. English translation in U. of California Computing Center, Tech. Report. No. 5, Berkeley, CA, 1966.
Atro Voutilainen and Pasi Tapanainen. 1993. Ambiguity resolution in a reductionistic parser. In 6th EACL 1993, Proceedings of the Conference, pages 394–403, Utrecht, The Netherlands.
Atro Voutilainen. 1994. Designing a Parsing Grammar. Number 22 in Publications of the Department of General Linguistics, University of Helsinki. Yliopistopaino, Helsinki.
Anssi Mikael Yli-Jyrä and Kimmo Koskenniemi. 2004. Compiling contextual restrictions on strings into finite-state automata. In Loek Cleophas and Bruce W. Watson, editors, The Eindhoven FASTAR Days, Proceedings, number 04/40 in Computer Science Reports, Eindhoven, The Netherlands, December. Technische Universiteit Eindhoven.
Anssi Mikael Yli-Jyrä. 2003. Describing syntax with star-free regular expressions. In 11th EACL 2003, Proceedings of the Conference, pages 379–386, Agro Hotel, Budapest, Hungary, April 12–17.
Anssi Yli-Jyrä. 2008. Transducers from parallel replace rules and modes with generalized lenient composition. In Finite-State Methods and Natural Language Processing, 6th International Workshop, FSMNL-2007, pages 197–212, Potsdam. Potsdam University Press.
Anssi Yli-Jyrä. 2011. An efficient constraint grammar parser based on inward deterministic automata. In Proceedings of the NODALIDA 2011 workshop Constraint Grammar Applications, May 11, 2011, volume 14 of NEALT Proceedings Series, Riga, Latvia.
Anssi Yli-Jyrä. unpublished. Efficient contextsensitive rewriting with inward deterministic transducers. Manuscript, 11 pages. Archived to Easy-Chair as a submission to PSC 2010 (Prague Stringology Conference 2010).
