On the public citation graph

Testing equivalence of morphisms on context-free languages

0 signed · 141 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/jcss.1995.1002openalex-snapshot

Polynomial Size Test Sets For Context-Free Languages

inferredcites →https://doi.org/10.1007/3-540-55124-7_4openalex-snapshot

Makanin's algorithm for word equations-two improvements and a generalization

inferredcites →https://doi.org/10.1007/3-540-55719-9_63openalex-snapshot

Polynomial size test sets for context-free languages

inferredcites →https://doi.org/10.1016/0304-3975(93)90325-nopenalex-snapshot

Efficient constructions of test sets for regular and context-free languages

inferredcites →https://doi.org/10.1016/s0019-9958(82)80028-4openalex-snapshot

Test sets for context free languages and algebraic systems of equations over a free monoid

inferredcites →https://doi.org/10.1070/sm1977v032n02abeh002376openalex-snapshot

THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

inferredcites →https://doi.org/10.1109/fscs.1990.89605openalex-snapshot

Complexity of unification in free groups and free semi-groups

inferredcites →https://doi.org/10.1145/78935.78938openalex-snapshot

Minimal and complete word unification

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jcss.2002.1852openalex-snapshot

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts

inferred← citeshttps://doi.org/10.1007/11532231_11openalex-snapshot

Well-Nested Context Unification

inferred← citeshttps://doi.org/10.1007/11601524_13openalex-snapshot

Efficient Memory Representation of XML Documents

inferred← citeshttps://doi.org/10.1007/11605157_7openalex-snapshot

Prime Normal Form and Equivalence of Simple Grammars

inferred← citeshttps://doi.org/10.1007/11805618_30openalex-snapshot

Bounded Second-Order Unification Is NP-Complete

inferred← citeshttps://doi.org/10.1007/11814771_8openalex-snapshot

Stratified Context Unification Is NP-Complete

inferred← citeshttps://doi.org/10.1007/11821069_56openalex-snapshot

Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes

inferred← citeshttps://doi.org/10.1007/11821069_59openalex-snapshot

Querying and Embedding Compressed Texts

inferred← citeshttps://doi.org/10.1007/11924661_22openalex-snapshot

XML Validation for Context-Free Grammars

inferred← citeshttps://doi.org/10.1007/3-540-44693-1_15openalex-snapshot

The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete

inferred← citeshttps://doi.org/10.1007/3-540-45007-6_6openalex-snapshot

Test Sets for Large Families of Languages

inferred← citeshttps://doi.org/10.1007/3-540-45995-2_31openalex-snapshot

Pattern Matching and Membership for Hierarchical Message Sequence Charts

inferred← citeshttps://doi.org/10.1007/3-540-47849-3_3openalex-snapshot

Algorithms on Compressed Strings and Arrays

inferred← citeshttps://doi.org/10.1007/3-540-60044-2_44openalex-snapshot

Pattern-matching for strings with short descriptions

inferred← citeshttps://doi.org/10.1007/3-540-61258-0_3openalex-snapshot

Randomized efficient algorithms for compressed strings: the finger-print approach

inferred← citeshttps://doi.org/10.1007/3-540-61422-2_148openalex-snapshot

Efficient algorithms for Lempel-Ziv encoding

inferred← citeshttps://doi.org/10.1007/3-540-63220-4_48openalex-snapshot

On the complexity of pattern matching for highly compressed two-dimensional texts

inferred← citeshttps://doi.org/10.1007/978-0-387-09680-3_6openalex-snapshot

Literal Shuffle of Compressed Words

inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9openalex-snapshot

The Compressed Word Problem for Groups

inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9_3openalex-snapshot

Algorithms on Compressed Words

inferred← citeshttps://doi.org/10.1007/978-3-030-00250-3_9openalex-snapshot

Certain Query Answering on Compressed String Patterns: From Streams to Hyperstreams

inferred← citeshttps://doi.org/10.1007/978-3-030-40608-0_4openalex-snapshot

Recompression: Technique for Word Equations and Compressed Data

inferred← citeshttps://doi.org/10.1007/978-3-030-48516-0_16openalex-snapshot

Equivalence of Linear Tree Transducers with Output in the Free Group

inferred← citeshttps://doi.org/10.1007/978-3-030-80049-9_30openalex-snapshot

Compression Techniques in Group Theory

inferred← citeshttps://doi.org/10.1007/978-3-319-06686-8_19openalex-snapshot

Processing Succinct Matrices and Vectors

inferred← citeshttps://doi.org/10.1007/978-3-319-21500-6_3openalex-snapshot

Grammar-Based Tree Compression

inferred← citeshttps://doi.org/10.1007/978-3-319-23660-5_2openalex-snapshot

Equality Testing of Compressed Strings

inferred← citeshttps://doi.org/10.1007/978-3-319-90530-3_11openalex-snapshot

Grammar-Based Compression of Unranked Trees

inferred← citeshttps://doi.org/10.1007/978-3-540-24727-2_26openalex-snapshot

Tree Transducers and Tree Compressions

inferred← citeshttps://doi.org/10.1007/978-3-540-25979-4_4openalex-snapshot

Monadic Second-Order Unification Is NP-Complete

inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_5openalex-snapshot

Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input

inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_76openalex-snapshot

Word Problems on Compressed Words

inferred← citeshttps://doi.org/10.1007/978-3-540-32254-2_10openalex-snapshot

Decidable Variants of Higher-Order Unification

inferred← citeshttps://doi.org/10.1007/978-3-540-69738-1_26openalex-snapshot

Assertion Checking Unified

inferred← citeshttps://doi.org/10.1007/978-3-540-71316-6_18openalex-snapshot

Computing Procedure Summaries for Interprocedural Analysis

inferred← citeshttps://doi.org/10.1007/978-3-540-71389-0_25openalex-snapshot

Complexity Results on Balanced Context-Free Languages

inferred← citeshttps://doi.org/10.1007/978-3-540-73437-6_24openalex-snapshot

Processing Compressed Texts: A Tractability Border

inferred← citeshttps://doi.org/10.1007/978-3-540-73595-3_11openalex-snapshot

Logical Interpretation: Static Program Analysis Using Theorem Proving

inferred← citeshttps://doi.org/10.1007/978-3-540-74510-5_26openalex-snapshot

Efficient Computation in Groups Via Compression

inferred← citeshttps://doi.org/10.1007/978-3-540-77566-9_31openalex-snapshot

Computing Longest Common Substring and All Palindromes from Compressed Strings

inferred← citeshttps://doi.org/10.1007/978-3-642-00596-1_16openalex-snapshot

Parameter Reduction in Grammar-Compressed Trees

inferred← citeshttps://doi.org/10.1007/978-3-642-02348-4_26openalex-snapshot

Unification with Singleton Tree Grammars

inferred← citeshttps://doi.org/10.1007/978-3-642-02737-6_8openalex-snapshot

The Inclusion Problem of Context-Free Languages: Some Tractable Cases

inferred← citeshttps://doi.org/10.1007/978-3-642-03351-3_23openalex-snapshot

Compressed Word Problems in HNN-Extensions and Amalgamated Products

inferred← citeshttps://doi.org/10.1007/978-3-642-03409-1_28openalex-snapshot

Equivalence of Deterministic Nested Word to Word Transducers

inferred← citeshttps://doi.org/10.1007/978-3-642-14455-4_21openalex-snapshot

Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups

inferred← citeshttps://doi.org/10.1007/978-3-642-15155-2_32openalex-snapshot

Properties of Visibly Pushdown Transducers

inferred← citeshttps://doi.org/10.1007/978-3-642-20712-9_21openalex-snapshot

Compressed Membership in Automata with Compressed Labels

inferred← citeshttps://doi.org/10.1007/978-3-642-22012-8_16openalex-snapshot

Isomorphism of Regular Trees and Words

inferred← citeshttps://doi.org/10.1007/978-3-642-22993-0_41openalex-snapshot

Compressed Word Problems for Inverse Monoids

inferred← citeshttps://doi.org/10.1007/978-3-642-24364-6_16openalex-snapshot

Congruence Closure of Compressed Terms in Polynomial Time

inferred← citeshttps://doi.org/10.1007/978-3-642-31365-3_32openalex-snapshot

New Algorithms for Unification Modulo One-Sided Distributivity and Its Variants

inferred← citeshttps://doi.org/10.1007/978-3-642-31594-7_45openalex-snapshot

Faster Fully Compressed Pattern Matching by Recompression

inferred← citeshttps://doi.org/10.1007/978-3-642-38905-4_17openalex-snapshot

Approximation of Grammar-Based Compression via Recompression

inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_37openalex-snapshot

Parallel Identity Testing for Skew Circuits with Big Powers and Applications

inferred← citeshttps://doi.org/10.1007/978-3-662-53132-7_29openalex-snapshot

Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time

inferred← citeshttps://doi.org/10.1007/bfb0055097openalex-snapshot

Application of Lempel-Ziv encodings to the solution of word equations

inferred← citeshttps://doi.org/10.1007/s00224-010-9295-2openalex-snapshot

Compressed Word Problems in HNN-extensions and Amalgamated Products

inferred← citeshttps://doi.org/10.1007/s00224-013-9443-6openalex-snapshot

The Complexity of Compressed Membership Problems for Finite Automata

inferred← citeshttps://doi.org/10.1007/s00224-014-9544-xopenalex-snapshot

XML Compression via Directed Acyclic Graphs

inferred← citeshttps://doi.org/10.1007/s00224-015-9666-9openalex-snapshot

Processing Succinct Matrices and Vectors

inferred← citeshttps://doi.org/10.1007/s00224-019-09942-yopenalex-snapshot

Grammar-Based Compression of Unranked Trees

inferred← citeshttps://doi.org/10.1007/s10990-013-9093-zopenalex-snapshot

Functional programs as compressed data

inferred← citeshttps://doi.org/10.1016/j.ic.2005.04.002openalex-snapshot

The existential theory of equations with rational constraints in free groups is PSPACE-complete

inferred← citeshttps://doi.org/10.1016/j.ic.2011.01.009openalex-snapshot

Leaf languages and string compression

inferred← citeshttps://doi.org/10.1016/j.ic.2013.01.002openalex-snapshot

Isomorphism of regular trees and words

inferred← citeshttps://doi.org/10.1016/j.ic.2014.07.003openalex-snapshot

Static analysis of XML security views and query rewriting

inferred← citeshttps://doi.org/10.1016/j.ipl.2012.01.008openalex-snapshot

Fast equality test for straight-line compressed strings

inferred← citeshttps://doi.org/10.1016/j.ipl.2018.01.002openalex-snapshot

Balancedness of MSO transductions in polynomial time

inferred← citeshttps://doi.org/10.1016/j.is.2008.01.004openalex-snapshot

Efficient memory representation of XML document trees

inferred← citeshttps://doi.org/10.1016/j.is.2013.06.006openalex-snapshot

XML tree structure compression using RePair

inferred← citeshttps://doi.org/10.1016/j.jalgebra.2022.01.001openalex-snapshot

The compressed word problem in relatively hyperbolic groups

inferred← citeshttps://doi.org/10.1016/j.jcss.2012.03.003openalex-snapshot

Parameter reduction and automata evaluation for grammar-compressed trees

inferred← citeshttps://doi.org/10.1016/j.jcss.2018.05.002openalex-snapshot

Visibly pushdown transducers

inferred← citeshttps://doi.org/10.1016/j.tcs.2004.09.017openalex-snapshot

Explicit test sets for iterated morphisms in free monoids and metabelian groups

inferred← citeshttps://doi.org/10.1016/j.tcs.2006.07.021openalex-snapshot

Prime normal form and equivalence of simple grammars

inferred← citeshttps://doi.org/10.1016/j.tcs.2008.12.016openalex-snapshot

Efficient algorithms to compute compressed longest common substrings and compressed palindromes

inferred← citeshttps://doi.org/10.1016/j.tcs.2015.05.027openalex-snapshot

Approximation of grammar-based compression via recompression

inferred← citeshttps://doi.org/10.1016/j.tcs.2015.12.032openalex-snapshot

A really simple approximation of smallest grammar

inferred← citeshttps://doi.org/10.1017/s0960129518000208openalex-snapshot

Linear pattern matching of compressed terms and polynomial rewriting

inferred← citeshttps://doi.org/10.1090/mcom/3392openalex-snapshot

Polynomial braid combing

inferred← citeshttps://doi.org/10.1090/tran/8623openalex-snapshot

Logspace and compressed-word computations in nilpotent groups

inferred← citeshttps://doi.org/10.1093/jigpal/jzq010openalex-snapshot

On the complexity of Bounded Second-Order Unification and Stratified Context Unification

inferred← citeshttps://doi.org/10.1109/5.892712openalex-snapshot

Compressed and fully compressed pattern matching in one and two dimensions

inferred← citeshttps://doi.org/10.1109/dcc.2011.42openalex-snapshot

Tree Structure Compression with RePair

inferred← citeshttps://doi.org/10.1109/focs.2015.62openalex-snapshot

Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable

inferred← citeshttps://doi.org/10.1109/lics.2008.17openalex-snapshot

Context Matching for Compressed Terms

inferred← citeshttps://doi.org/10.1109/sffcs.1999.814622openalex-snapshot

Satisfiability of word equations with constants is in PSPACE

inferred← citeshttps://doi.org/10.1137/050645403openalex-snapshot

The Complexity of Monadic Second-Order Unification

inferred← citeshttps://doi.org/10.1137/s0097539704445950openalex-snapshot

Word Problems and Membership Problems on Compressed Words

inferred← citeshttps://doi.org/10.1142/s012905411000757xopenalex-snapshot

COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA

inferred← citeshttps://doi.org/10.1142/s0129054115400134openalex-snapshot

A Survey on Decidable Equivalence Problems for Tree Transducers

inferred← citeshttps://doi.org/10.1142/s021819671000542xopenalex-snapshot

COMPRESSED WORDS AND AUTOMORPHISMS IN FULLY RESIDUALLY FREE GROUPS

inferred← citeshttps://doi.org/10.1142/s0218196712400073openalex-snapshot

COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS

inferred← citeshttps://doi.org/10.1142/s0218196712500476openalex-snapshot

POWER CIRCUITS, EXPONENTIAL ALGEBRA, AND TIME COMPLEXITY

inferred← citeshttps://doi.org/10.1142/s0218196715400056openalex-snapshot

SLP compression for solutions of equations with constraints in free and hyperbolic groups

inferred← citeshttps://doi.org/10.1145/1938551.1938560openalex-snapshot

View update translation for XML

inferred← citeshttps://doi.org/10.1145/1970398.1970402openalex-snapshot

Unification and matching on compressed terms

inferred← citeshttps://doi.org/10.1145/2103746.2103770openalex-snapshot

Functional programs as compressed data

inferred← citeshttps://doi.org/10.1145/2448496.2448506openalex-snapshot

XML compression via DAGs

inferred← citeshttps://doi.org/10.1145/2631920openalex-snapshot

Faster Fully Compressed Pattern Matching by Recompression

inferred← citeshttps://doi.org/10.1145/2743014openalex-snapshot

Recompression

inferred← citeshttps://doi.org/10.1145/3055399.3055442openalex-snapshot

Randomized polynomial time identity testing for noncommutative circuits

inferred← citeshttps://doi.org/10.1145/3182653openalex-snapshot

Equivalence of Deterministic Top-Down Tree-to-String Transducers Is Decidable

inferred← citeshttps://doi.org/10.1145/3452143.3465530openalex-snapshot

Cyclotomic Identity Testing and Applications

inferred← citeshttps://doi.org/10.1145/3569708openalex-snapshot

Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems

inferred← citeshttps://doi.org/10.1145/3571266openalex-snapshot

Context-Bounded Verification of Context-Free Specifications

inferred← citeshttps://doi.org/10.1145/990308.990312openalex-snapshot

Satisfiability of word equations with constants is in PSPACE

inferred← citeshttps://doi.org/10.1515/gcc-2012-0016openalex-snapshot

Algorithmics on SLP-compressed strings: A survey

inferred← citeshttps://doi.org/10.2168/lmcs-11(2:11)2015openalex-snapshot

On Unification Modulo One-Sided Distributivity: Algorithms, Variants and Asymmetry

inferred← citeshttps://doi.org/10.23638/lmcs-13(2:5)2017openalex-snapshot

Inter-procedural Two-Variable Herbrand Equalities

inferred← citeshttps://doi.org/10.4086/toc.2019.v015a007openalex-snapshot

inferred← citeshttps://doi.org/10.4171/cmh/142openalex-snapshot

Polynomial-time word problems

inferred← citeshttps://doi.org/10.4204/eptcs.110.5openalex-snapshot

Linear Compressed Pattern Matching for Polynomial Rewriting (Extended Abstract)

inferred← citeshttps://doi.org/10.4204/eptcs.151.5openalex-snapshot

Equivalence Problems for Tree Transducers: A Brief Survey

inferred← citeshttps://doi.org/10.4230/lipics.ecoop.2017.19openalex-snapshot

Optimal Test Sets for Context-Free Languages

inferred← citeshttps://doi.org/10.4230/lipics.rta.2012.272openalex-snapshot

Matching of Compressed Patterns with Character-Variables

inferred← citeshttps://doi.org/10.4230/lipics.stacs.2012.136openalex-snapshot

Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)

inferred← citeshttps://doi.org/10.4230/lipics.stacs.2018.48openalex-snapshot

Computing the Longest Common Prefix of a Context-free Language in Polynomial Time

inferred← citeshttps://doi.org/10.4230/lipics.stacs.2019.37openalex-snapshot

Compressed Decision Problems in Hyperbolic Groups

inferred← citeshttps://doi.org/10.46298/dmtcs.526openalex-snapshot

Grammatical compression: compressed equivalence and other problems

inferred← citeshttps://doi.org/10.48550/arxiv.0811.3303openalex-snapshot

Compressed word problems in HNN-extensions and amalgamated products

inferred← citeshttps://doi.org/10.48550/arxiv.1106.1000openalex-snapshot

Compressed word problems for inverse monoids

inferred← citeshttps://doi.org/10.48550/arxiv.1111.3244openalex-snapshot

Faster fully compressed pattern matching by recompression

inferred← citeshttps://doi.org/10.48550/arxiv.1301.5842openalex-snapshot

Approximation of grammar-based compression via recompression

inferred← citeshttps://doi.org/10.48550/arxiv.1402.3452openalex-snapshot

Processing Succinct Matrices and Vectors

inferred← citeshttps://doi.org/10.48550/arxiv.1403.4445openalex-snapshot

A really simple approximation of smallest grammar

inferred← citeshttps://doi.org/10.48550/arxiv.1502.04625openalex-snapshot

Compressed Tree Canonization

inferred← citeshttps://doi.org/10.48550/arxiv.1503.09163openalex-snapshot

Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable

inferred← citeshttps://doi.org/10.48550/arxiv.1609.09392openalex-snapshot

Polynomial-time algorithms for the curve graph

inferred← citeshttps://doi.org/10.48550/arxiv.2010.14181openalex-snapshot

Impossibility Results for Grammar-Compressed Linear Algebra

inferred← citeshttps://doi.org/10.5821/dissertation-2117-95490openalex-snapshot

Variants of unification considering compression and context variables

inferred← citeshttps://doi.org/10.70675/1c02061eze223z4fbfzb6fdzf9a2f187469dopenalex-snapshot

Certain query answering on hyperstreams

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.