About: We study the computational complexity of finite intersections and unions of deterministic context-free languages. Earlier, Wotschke (1978) demonstrated that intersections of [Formula: see text] deterministic context-free languages are in general more powerful than intersections of d deterministic context-free languages for any positive integer d based on the hierarchy separation of Liu and Weiner (1973). The argument of Liu and Weiner, however, works only on bounded languages of particular forms, and therefore Wotschke’s result cannot be extended to disprove any other language to be written in the form of an intersection of d deterministic context-free languages. To deal with the non-membership of a wide range of languages, we circumvent their proof argument and instead devise a new, practical technical tool: a pumping lemma for finite unions of deterministic context-free languages. Since the family of deterministic context-free languages is closed under complementation, this pumping lemma enables us to show a non-membership relation of languages made up with finite intersections of even non-bounded languages as well. We also refer to a relationship to Hibbard’s limited automata.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : wasabi.inria.fr associated with source document(s)

AttributesValues
type
value
  • We study the computational complexity of finite intersections and unions of deterministic context-free languages. Earlier, Wotschke (1978) demonstrated that intersections of [Formula: see text] deterministic context-free languages are in general more powerful than intersections of d deterministic context-free languages for any positive integer d based on the hierarchy separation of Liu and Weiner (1973). The argument of Liu and Weiner, however, works only on bounded languages of particular forms, and therefore Wotschke’s result cannot be extended to disprove any other language to be written in the form of an intersection of d deterministic context-free languages. To deal with the non-membership of a wide range of languages, we circumvent their proof argument and instead devise a new, practical technical tool: a pumping lemma for finite unions of deterministic context-free languages. Since the family of deterministic context-free languages is closed under complementation, this pumping lemma enables us to show a non-membership relation of languages made up with finite intersections of even non-bounded languages as well. We also refer to a relationship to Hibbard’s limited automata.
subject
  • Automata (computation)
  • Basic concepts in set theory
  • Binary operations
  • Formal languages
  • Lemmas
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software