context-free grammar

---

context-free grammar

Tag #context-free grammar

132 papers:

DLT-2019-BroughCP #problem #word

Context-Free Word Problem Semigroups (TB, AJC, MP), pp. 292–305.

SLE-2019-RaselimoF #fault #locality

Spectrum-based fault localization for context-free grammars (MR, BF0), pp. 15–28.

DLT-2018-CarpiD #commutative #equivalence #on the

On the Commutative Equivalence of Context-Free Languages (AC, FD), pp. 169–181.

DLT-2018-Rubtsov

A Structural Lemma for Deterministic Context-Free Languages (AAR), pp. 553–565.

CIAA-2016-Teichmann #approximate #linear

Regular Approximation of Weighted Linear Nondeleting Context-Free Tree Languages (MT), pp. 273–284.

DLT-2016-Denkinger #automaton #multi

An Automata Characterisation for Multiple Context-Free Languages (TD), pp. 138–150.

CIAA-2015-Prusa #decidability #multi #problem

(Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars (DP), pp. 250–262.

ICALP-v1-2015-GoldreichGR #branch #proving #proximity #source code

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs — (OG, TG, RDR), pp. 666–677.

TLCA-2015-AfshariHL

Herbrand Disjunctions, Cut Elimination and Context-Free Tree Grammars (BA, SH, GEL), pp. 1–16.

POPL-2015-BastaniAA #reachability #specification #using

Specification Inference Using Context-Free Language Reachability (OB, SA, AA), pp. 553–566.

CC-2015-HollingumS #framework #reachability #scalability #towards

Towards a Scalable Framework for Context-Free Language Reachability (NH, BS), pp. 193–211.

CC-2015-PingaliB #parsing #visual notation

A Graphical Model for Context-Free Grammar Parsing (KP, GB), pp. 3–27.

DLT-J-2013-BertoniCD14 #automaton #decidability #on the #problem #quantum

On the Decidability of the Intersection Problem for Quantum Automata and Context-Free Languages (AB, CC, FD), pp. 1065–1082.

DLT-J-2013-DrosteV14 #theorem

The Chomsky-SCHüTzenberger Theorem for Quantitative Context-Free Languages (MD, HV), pp. 955–970.

CIAA-2014-Osterholzer #automaton

Pushdown Machines for Weighted Context-Free Tree Translation (JO), pp. 290–303.

DLT-2014-Sorokin

Pumping Lemma and Ogden Lemma for Displacement Context-Free Grammars (AS), pp. 154–165.

RTA-TLCA-2014-CreusG #automation #evaluation

Automatic Evaluation of Context-Free Grammars (CC, GG), pp. 139–148.

SLE-2014-Ridge #combinator #parsing #performance #using

Simple, Efficient, Sound and Complete Combinator Parsing for All Context-Free Grammars, Using an Oracle (TR), pp. 261–281.

DLT-J-2012-EsikO13 #on the #word

On Context-Free Languages of Scattered Words (ZÉ, SO), pp. 1029–1048.

DLT-J-2012-HanKS13 #regular expression

The Edit-Distance between a Regular Language and a Context-Free Language (YSH, SKK, KS), pp. 1067–1082.

DLT-J-2012-LehtinenO13 #morphism

Homomorphisms Preserving Deterministic Context-Free Languages (TL, AO), pp. 1049–1066.

CIAA-2013-HanKS #approximate #automaton #finite

Approximate Matching between a Context-Free Grammar and a Finite-State Automaton (YSH, SKK, KS), pp. 146–157.

DLT-2013-BertoniCD #automaton #decidability #finite #linear #problem #quantum

Quantum Finite Automata and Linear Context-Free Languages: A Decidable Problem (AB, CC, FD), pp. 82–93.

DLT-2013-DrosteV #theorem

The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages (MD, HV), pp. 203–214.

ICALP-v2-2013-EtessamiSY #probability #regular expression

Stochastic Context-Free Grammars, Regular Languages, and Newton’s Method (KE, AS, MY), pp. 199–211.

ICFP-2013-BernardyC #divide and conquer #parsing #performance

Efficient divide-and-conquer parsing of practical context-free languages (JPB, KC), pp. 111–122.

WCRE-2012-BernatM #algebra #editing

Structured Binary Editing with a CFG Transformation Algebra (ARB, BPM), pp. 9–18.

AFL-J-2011-FazekasLS12 #on the

On Non-Primitive Palindromic Context-Free Languages (SZF, PL, KST), pp. 1277–1290.

DLT-2012-0002HOT #problem #word

Semigroups with a Context-Free Word Problem (MH, DFH, MDO, RMT), pp. 97–108.

DLT-2012-EsikO #on the #word

On Context-Free Languages of Scattered Words (ZÉ, SO), pp. 142–153.

DLT-2012-HanKS #regular expression

Computing the Edit-Distance between a Regular Language and a Context-Free Language (YSH, SKK, KS), pp. 85–96.

DLT-2012-HolzerJM

Generalized Derivations with Synchronized Context-Free Grammars (MH, SJ, IM), pp. 109–120.

DLT-2012-LavadoPS #automaton #nondeterminism

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata (GJL, GP, SS), pp. 284–295.

DLT-2012-LehtinenO #morphism

Homomorphisms Preserving Deterministic Context-Free Languages (TL, AO), pp. 154–165.

LATA-2012-BarashO

Defining Contexts in Context-Free Grammars (MB, AO), pp. 106–118.

LATA-2012-Yoshinaka #integration #learning

Integration of the Dual Approaches in the Distributional Learning of Context-Free Grammars (RY), pp. 538–550.

STOC-2012-EtessamiSY #algorithm #branch #multi #polynomial #probability #process

Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars (KE, AS, MY), pp. 579–588.

ICDAR-2011-AlvaroSB #2d #probability #recognition #using

Recognition of Printed Mathematical Expressions Using Two-Dimensional Stochastic Context-Free Grammars (FA, JAS, JMB), pp. 1225–1229.

DLT-J-2009-BertoniCR11 #problem

The Inclusion Problem of Context-Free Languages: Some Tractable Cases (AB, CC, RR), pp. 289–299.

AFL-2011-IvanM #generative #word

Müller context-free grammars generating well-ordered words (SI, ÁM), pp. 225–240.

DLT-2011-KortelainenS #bound

There Does Not Exist a Minimal Full Trio with Respect to Bounded Context-Free Languages (JK, TS), pp. 312–323.

DLT-2011-Yoshinaka #concept #learning #towards

Towards Dual Approaches for Learning Context-Free Grammars Based on Syntactic Concept Lattices (RY), pp. 429–440.

SLE-2011-FischerLZ #comparison #parsing #testing

Comparison of Context-Free Grammars Based on Parsing Generated Test Data (BF, RL, VZ), pp. 324–343.

FoSSaCS-2011-MollerS #html #validation

HTML Validation of Context-Free Languages (AM, MS), pp. 426–440.

VMCAI-2011-BardinHV #re-engineering #source code

Refinement-Based CFG Reconstruction from Unstructured Programs (SB, PH, FV), pp. 54–69.

DLT-J-2008-GawrychowskiKRS10 #polynomial

Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time (PG, DK, NR, JS), pp. 597–618.

DLT-2010-DassowM #on the #strict

On Restricted Context-Free Grammars (JD, TM), pp. 434–435.

DLT-2010-EsikI #on the

On Müller Context-Free Grammars (ZÉ, SI), pp. 173–184.

LATA-2010-KanazawaS #multi #power of

The Copying Power of Well-Nested Multiple Context-Free Grammars (MK, SS), pp. 344–355.

LATA-2010-Leupold #word

Primitive Words Are Unavoidable for Context-Free Languages (PL), pp. 403–413.

LATA-2010-WeinbergN #probability

Extending Stochastic Context-Free Grammars for an Application in Bioinformatics (FW, MEN), pp. 585–595.

LATA-2010-YoshinakaKS #multi

Chomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages (RY, YK, HS), pp. 596–607.

SEFM-2010-XuZC #generative #tool support

A Toolkit for Generating Sentences from Context-Free Grammars (ZX, LZ, HC), pp. 118–122.

CSL-2010-BarthwalN #formal method #normalisation

A Formalisation of the Normal Forms of Context-Free Grammars in HOL4 (AB, MN), pp. 95–109.

DLT-2009-BertoniCR #problem

The Inclusion Problem of Context-Free Languages: Some Tractable Cases (AB, CC, RR), pp. 103–112.

DLT-2009-Egecioglu #approximate

Strongly Regular Grammars and Regular Approximation of Context-Free Languages (ÖE), pp. 207–220.

DLT-2009-Kanazawa #multi

The Pumping Lemma for Well-Nested Multiple Context-Free Languages (MK), pp. 312–325.

LATA-2009-Masopust #generative #power of

A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions (TM), pp. 554–565.

LDTA-2008-Basten09 #ambiguity #detection #usability

The Usability of Ambiguity Detection Methods for Context-Free Grammars (BB), pp. 35–46.

DLT-J-2007-Ravikumar08 #ambiguity

The Benford-Newcomb Distribution and Unambiguous Context-Free Languages (BR), pp. 717–727.

CIAA-2008-Fujiyoshi #automaton

Combination of Context-Free Grammars and Tree Automata for Unranked and Ranked Trees (AF), pp. 283–285.

DLT-2008-GawrychowskiKRS #polynomial

Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time (PG, DK, NR, JS), pp. 339–358.

ICALP-B-2008-AxelssonHL #incremental #satisfiability #using

Analyzing Context-Free Grammars Using an Incremental SAT Solver (RA, KH, ML), pp. 410–422.

PPDP-2008-ThiemannN #metaprogramming

Macros for context-free grammars (PT, MN), pp. 120–130.

ATEM-J-2006-DubeyJA #learning #set

Learning context-free grammar rules from a set of program (AD, PJ, SKA), pp. 223–240.

CIAA-2007-BrabrandGM #ambiguity

Analyzing Ambiguity of Context-Free Grammars (CB, RG, AM), pp. 214–225.

CIAA-2007-CaucalCFR #performance #throughput

Efficient Computation of Throughput Values of Context-Free Languages (DC, JC, WF, WR), pp. 203–213.

CIAA-2007-MrazPO #nondeterminism

A Measure for the Degree of Nondeterminism of Context-Free Languages (FM, MP, FO), pp. 192–202.

DLT-2007-MalcherP #bound #complexity

Descriptional Complexity of Bounded Context-Free Languages (AM, GP), pp. 312–323.

ICALP-2007-Schmitz #ambiguity #detection

Conservative Ambiguity Detection in Context-Free Grammars (SS), pp. 692–703.

SEKE-2007-SilvaMPV #evolution #grammar inference #xml

XML Schema Evolution by Context Free Grammar Inference (JCTdS, MAM, ATRP, SRV), p. 444–?.

FoSSaCS-2007-TozawaM #complexity

Complexity Results on Balanced Context-Free Languages (AT, YM), pp. 346–360.

DLT-2006-BastienCFR #equivalence

Equivalence of Functions Represented by Simple Context-Free Grammars with Output (CB, JC, WF, WR), pp. 71–82.

DLT-2006-BertoniCP #xml

Context-Free Grammars and XML Languages (AB, CC, BP), pp. 108–119.

SEKE-2006-JavedMSB #domain-specific language #incremental

Incrementally Inferring Context-Free Grammars for Domain-Specific Languages (FJ, MM, APS, BRB), pp. 363–368.

ICDAR-2005-HandleyNZ #comprehension #documentation #probability #using

Document Understanding System Using Stochastic Context-Free Grammars (JCH, AMN, RZ), pp. 511–515.

CIAA-J-2004-BordihnHK05 #problem #subclass

Unsolvability levels of operation problems for subclasses of context-free languages (HB, MH, MK), pp. 423–440.

SIGIR-2005-ViolaN #learning #using

Learning to extract information from semi-structured text using a discriminative context free grammar (PAV, MN), pp. 330–337.

LDTA-2005-CrepinsekMBJS #domain-specific language

Inferring Context-Free Grammars for Domain-Specific Languages (MC, MM, BRB, FJ, APS), pp. 99–116.

DATE-2005-WenzelRKP #clustering #generative #model checking

utomatic Timing Model Generation by CFG Partitioning and Model Checking (IW, BR, RK, PPP), pp. 606–611.

CIAA-2004-BordihnHK #linear #problem

Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages (HB, MH, MK), pp. 68–79.

DLT-2004-InenagaST #algorithm #pattern matching #performance #subclass

An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars (SI, AS, MT), pp. 225–236.

DLT-2004-KutribMW #linear

The Boolean Closure of Linear Context-Free Languages (MK, AM, DW), pp. 284–295.

CIAA-2002-Bruggemann-KleinW #on the #parsing #predict

On Predictive Parsing and Extended Context-Free Grammars (ABK, DW), pp. 239–247.

ICML-2002-OatesDB #learning

Learning k-Reversible Context-Free Grammars from Positive Structural Examples (TO, DD, VB), pp. 459–465.

WCRE-J-1997-BrandSV00 #component #generative #legacy

Generation of components for software renovation factories from context-free grammars (MvdB, MPAS, CV), pp. 209–266.

IWPC-2000-PowerM #analysis

Metric-Based Analysis of Context-Free Grammars (JFP, BAM), pp. 171–178.

WLC-2000-DomosiK

An Improvement of Iteration Lemmata for Context-free Languages (PD, MK), pp. 185–191.

DLT-1999-Wich #ambiguity #exponential

Exponential ambiguity of context-free grammars (KW), pp. 125–138.

ICML-1999-SakakibaraK #learning #using

GA-based Learning of Context-Free Grammars using Tabular Representations (YS, MK), pp. 354–360.

WIA-1998-AlbertGW #algorithm #normalisation

Extended Context-Free Grammars and Normal Form Algorithms (JA, DG, DW), pp. 1–12.

ICFP-1998-Haiming #recursion

Combining CFG and Recursive Functions to Get a New Language (HC), p. 351.

WCRE-1997-BrandSV #component #generative #legacy

Generation of Components for Software Renovation Factories from Context-Free Grammars (MvdB, MPAS, CV), p. 144–?.

DLT-1997-DassowMP

Point mutations in context-free languages (JD, VM, GP), pp. 429–446.

DLT-1997-MateescuSY #decidability

Decidability of fairness for context-free languages (AM, KS, SY), pp. 351–364.

DLT-1997-Zhiltsova #probability

An Optimal Coding for Stochastic Context-Free Languages with Unique Derivation (LPZ), pp. 539–550.

WIA-1997-Miller #algorithm #normalisation #towards

Towards a Meta-Normal Form Algorithm for Context-Free Grammars (CLM), pp. 133–143.

PEPM-1997-MelskiR #constraints #reachability #set

Interconveritibility of Set Constraints and Context-Free Language Reachability (DM, TWR), pp. 74–89.

DLT-1995-Asveld #parsing #recognition #robust #towards

Towards Robustness in Parsing — Fuzzifying Context-Free Language Recognition (PRJA), pp. 443–453.

DLT-1995-Georgescu #complexity #metric #orthogonal

The Orthogonality of Some Complexity Measures of Context-Free Languages (GG), pp. 73–78.

DLT-1995-JancarMPPV #automaton

Restarting Automata, Marcus Grammars and Context-Free Languages (PJ, FM, MP, MP, JV), pp. 102–111.

DLT-1995-MateiT

(0, 1)-Total Pure Context-Free Grammars (CM, FLT), pp. 148–153.

DLT-1995-SalomaaY #nondeterminism

Nondeterminism Degrees for Context-Free Languages (KS, SY), pp. 154–165.

SAC-1995-Cheung #ambiguity

Ambiguity in context-free grammars (BSNC), pp. 272–276.

ICALP-1994-HotzP #analysis #performance

Fast Uniform Analysis of Coupled-Context-Free Languages (GH, GP), pp. 412–423.

DLT-1993-EhrenfeuchtHPR

An Introduction to Context-free Text Grammars (AE, HJH, PtP, GR), pp. 357–369.

DLT-1993-Georgescu #on the

On the Index of Pure Context-free Grammars and Languages (GG), pp. 60–69.

DLT-1993-Raz #equivalence #multi

Deciding Multiplicity Equivalence for Certain Context-free Languages (DR), pp. 18–29.

ICALP-1992-KarhumakiPR #polynomial #testing

Polynomial Size Test Sets for Context-Free Languages (JK, WP, WR), pp. 53–64.

ICALP-1986-DymondR #memory management #parallel #recognition

Parallel RAMs with Owned Global Memory and Deterministic Context-Free Language Recognition (PWD, WLR), pp. 95–104.

ICALP-1982-Blum #on the #power of

On the Power of Chain Rules in Context Free Grammars (NB), pp. 72–82.

ICALP-1982-EhrenfeuchtHR

Conditions Enforcing Regularity of Context-Free Languages (AE, DH, GR), pp. 187–191.

ICALP-1980-AlbertC #equivalence #morphism #testing

Test Sets for Homomorphism Equivalence on Context Free Languages (JA, KCI), pp. 12–18.

ICALP-1979-Ruzzo #complexity #on the #parsing #recognition

On the Complexity of General Context-Free Language Parsing and Recognition (WLR), pp. 489–497.

ICALP-1977-Dieterich #fault #parsing

Parsing and Syntactic Error Recovery for Context-Free Grammars by Means of Coarse Structures (EWD), pp. 180–192.

ICALP-1977-DikovskyM #ambiguity #on the

On Three Types of Unambiguity of Context-Free Languages (AJD, LSM), pp. 193–205.

ICALP-1977-Walter #decidability #equivalence

Structural Equivalence of Context-Free Grammar Forms is Decidable (HKGW), pp. 539–553.

ICALP-1976-Linna #on the

On ω-sets Associated with Context-Free Languages (ML), pp. 1–19.

STOC-1976-GrahamHR #on the #polynomial #recognition

On Line Context Free Language Recognition in Less than Cubic Time (SLG, MAH, WLR), pp. 112–120.

STOC-1976-Sudborough #automaton #multi #on the #power of

On Deterministic Context-Free Languages, Multihead Automata, and the Power of an Auxiliary Pushdown Store (IHS), pp. 141–148.

ICALP-1974-Blattner #set

Transductions of Context-Free Languages into Sets of Sentential Forms (MB), pp. 511–522.

ICALP-1974-CremersG

Context-Free Grammar Forms (ABC, SG), pp. 364–382.

STOC-1974-BookNP #bound #linear #multi

Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (RVB, MN, MP), pp. 290–296.

STOC-1974-HuntR

Computational Parallels between the Regular and Context-Free Languages (HBHI, DJR), pp. 64–74.

STOC-1973-Greibach #polynomial

Jump PDA’s, Deterministic Context-Free Languages Principal AFDLs and Polynomial Time Recognition-Extended Abstract (SAG), pp. 20–28.

ICALP-1972-Baker #context-sensitive grammar #generative

Context-Sensitive Grammars Generating Context-Free Languages (BSB), pp. 501–506.

ICALP-1972-WeissMS #algebra #parsing

Algebraic Parsing Techniques for Context-Free Languages (SFW, GM, DFS), pp. 493–498.

STOC-1971-Terrine #algorithm #bottom-up #generative #parsing #set

An Algorithm Generating the Decision Table of a Deterministic Bottom Up Parser for a Subset of Context Free Grammars (GT), pp. 185–205.

STOC-1969-AhoU

Translations on a Context Free Grammar (AVA, JDU), pp. 93–112.

STOC-1969-PetersR #analysis #revisited

Context-Sensitive Immediate Constituent Analysis — Context-Free Languages Revisited (PSPJ, RWR), pp. 1–8.

STOC-1969-Rounds

Context-Free Grammars on Trees (WCR), pp. 143–148.

STOC-1969-Ullian #algorithm #ambiguity #problem

The Inherent Ambiguity Partial Algorithm Problem for Context Free Languages (JSU), pp. 19–20.