Skip to main content
Springer Nature Link
Log in

An Automata Characterisation for Multiple Context-Free Languages

  • Conference paper
  • First Online:
Developments in Language Theory (DLT 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9840))

Included in the following conference series:

Abstract

See More

We introduce tree stack automata as a new class of automata with storage and identify a restricted form of tree stack automata that recognises exactly the multiple context-free languages.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth <= buyboxMaxSingleColumnWidth && option != buyingOption) { hideBuyingOption(option) } }) var expanded = toggle.getAttribute("aria-expanded") === "true" || false toggle.setAttribute("aria-expanded", !expanded) form.hidden = expanded if (!expanded) { buyingOption.classList.add("expanded") } else { buyingOption.classList.remove("expanded") } priceInfo.hidden = expanded }, false) } } function hideBuyingOption(buyingOption) { var toggle = buyingOption.querySelector(".buying-option-price") var form = buyingOption.querySelector(".buying-option-form") var priceInfo = buyingOption.querySelector(".price-info") toggle.setAttribute("aria-expanded", false) form.hidden = true buyingOption.classList.remove("expanded") priceInfo.hidden = true } function initKeyControls() { document.addEventListener("keydown", function (event) { if (document.activeElement.classList.contains("buying-option-price") && (event.code === "Space" || event.code === "Enter")) { if (document.activeElement) { event.preventDefault() document.activeElement.click() } } }, false) } function initialStateOpen() { var buyboxWidth = buybox.offsetWidth ;[].slice.call(buybox.querySelectorAll(".buying-option")).forEach(function (option, index) { var toggle = option.querySelector(".buying-option-price") var form = option.querySelector(".buying-option-form") var priceInfo = option.querySelector(".price-info") if (buyboxWidth > buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The control flow of our constructed automaton is similar to that of the treewalk evaluator for attribute grammars [8, Sect. 3]. The two major differences are that the treewalk evaluator also treats inherited attributes (which are not present in PMCFGs) and that our constructed automaton generates the tree on the fly (while the treewalk evaluator is already provided with the tree).

  2. 2.

    The k-MCFG \(G({\mathcal {M}})\) exists since \([\![\cdot ]\!]\) is a homomorphism and k-MCFLs are closed under homomorphisms [13, Theorem 3.9].

References

  1. Aho, A.V.: Nested stack automata. JACM 16(3), 383–406 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  2. Chomsky, N.: Formal properties of grammars. In: Luce, R.D., Bush, R.R., Galanter, E. (eds.) Handbook of Mathematical Psychology, vol. 2. Wiley, New York (1962)

    Google Scholar 

  3. Villemonte de la Clergerie, É.: Parsing MCS languages with thread automata. In: Proceedings of TAG+02, pp. 101–108 (2002)

    Google Scholar 

  4. Villemonte de la Clergerie, É.: Parsing mildly context-sensitive languages with thread automata. In: Proceedings of COLING 2002, vol. 1, pp. 1–7. ACL (2002)

    Google Scholar 

  5. Engelfriet, J.: Context-free grammars with storage. CoRR (2014)

    Google Scholar 

  6. Guessarian, I.: Pushdown tree automata. Math. Syst. Theor. 16(1), 237–263 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  7. Herrmann, L., Vogler, H.: A Chomsky-Schützenberger theorem for weighted automata with storage. In: Maletti, A. (ed.) CAI 2015. LNCS, vol. 9270, pp. 115–127. Springer, Heidelberg (2015). doi:10.1007/978-3-319-23021-4_11

    Chapter  Google Scholar 

  8. Kennedy, K., Warren, S.K.: Automatic generation of efficient evaluators for attribute grammars. In: Proceedings of POPL 1976 (1976)

    Google Scholar 

  9. Kuhlmann, M., Satta, G.: Treebank grammar techniques for non-projective dependency parsing. In: Proceedings of EACL 2009, pp. 478–486. ACL (2009)

    Google Scholar 

  10. Maier, W.: Direct parsing of discontinuous constituents in German. In: Proceedings of SPMRL 2010, pp. 58–66. ACL (2010)

    Google Scholar 

  11. Schützenberger, M.P.: On context-free languages and push-down automata. Inf. Control 6(3), 246–264 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  12. Scott, D.: Some definitional suggestions for automata theory. J. Comput. Syst. Sci. 1(2), 187–212 (1967)

    Article  MATH  Google Scholar 

  13. Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. TCS 88(2), 191–229 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  14. Vijay-Shanker, K.: A study of tree adjoining grammars. Ph.D. thesis (1988)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Computer Science, Technische Universität Dresden, Nöthnitzer Str. 46, 01062, Dresden, Germany

    Tobias Denkinger

Authors
  1. Tobias Denkinger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tobias Denkinger .

Editor information

Editors and Affiliations

  1. Université du Québec à Montréal , Montreal, Québec, Canada

    Srečko Brlek

  2. Dept Mathematiques, Univ du Quebec Montreal Dept Mathematiques, Montreal, Québec, Canada

    Christophe Reutenauer

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Denkinger, T. (2016). An Automata Characterisation for Multiple Context-Free Languages. In: Brlek, S., Reutenauer, C. (eds) Developments in Language Theory. DLT 2016. Lecture Notes in Computer Science(), vol 9840. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53132-7_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-53132-7_12

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-53131-0

  • Online ISBN: 978-3-662-53132-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics