Finding Patterns Common to a Set of Strings

No abstract is available for this paper.

• Publication year

  1980

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  1980-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0022-0000(80)90041-0
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Inductive Inference of Formal Languages from Positive Data

  1980cited by this paper
• Complexity of Automaton Identification from Given Data

  1978cited by this paper
• Fast Pattern Matching in Strings

  1977cited by this paper
• The Problem of Solvability of Equations in a Free Semigroup

  1977cited by this paper
• Fast probabilistic algorithms for hamiltonian circuits and matchings

  1977cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• Formal languages and their relation to automata

  1969cited by this paper
• The SNOBOL4 programming language

  1968cited by this paper
• An Introduction to the Theory of Numbers

  1939cited by this paper

• Hardness of Regular Expression Matching with Extensions

  2026cites this paper
• On Generation in Metric Spaces

  2026cites this paper
• Quantifying Noise in Language Generation

  2026cites this paper
• Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds

  2026cites this paper
• On DoS Vulnerability of Regular Expressions, with and Without Backreferences

  2025cites this paper
• A Computational Cognitive Model for Processing Repetitions of Hierarchical Relations

  2025cites this paper
• Learning DFAs from Positive Examples Only via Word Counting

  2025cites this paper
• Solvable Tuple Patterns and Their Applications to Program Verification

  2025influential citation
• Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations

  2025cites this paper
• Pareto-optimal Non-uniform Language Generation

  2025cites this paper
• Positive Characteristic Sets for Relational Pattern Languages

  2025influential citation
• A Characterization of List Language Identification in the Limit

  2025cites this paper
• Dovetailing Pedagogy and Technology for Training with Time Travel

  2025cites this paper
• An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints

  2025influential citation
• Language Generation: Complexity Barriers and Implications for Learning

  2025influential citation
• FC-Datalog as a Framework for Efficient String Querying

  2025cites this paper
• Density Measures for Language Generation

  2025cites this paper
• Efficient Matching of Some Fundamental Regular Expressions with Backreferences

  2025influential citation
• Generation from Noisy Examples

  2025cites this paper
• The Computational Complexity of Positive Non-Clashing Teaching in Graphs

  2025cites this paper
• Word-Representable Graphs and Locality of Words

  2025cites this paper
• Representative Language Generation

  2025cites this paper
• On the computational and descriptional complexity of multi-pattern languages

  2025cites this paper
• Language Generation in the Limit: Noise, Loss, and Feedback

  2025cites this paper
• Disambiguation of Regular Expressions with Backreferences via Term Rewriting

  2024cites this paper
• Generation through the lens of learning theory

  2024influential citation
• k-local Graphs

  2024cites this paper
• The Equivalence Problem of E-Pattern Languages with Regular Constraints Is Undecidable

  2024influential citation
• Learning Tree Pattern Transformations

  2024cites this paper
• Languages Generated by Conjunctive Query Fragments of FC[REG]

  2024cites this paper
• Language Generation in the Limit

  2024cites this paper
• Exploring Facets of Language Generation in the Limit

  2024cites this paper
• On Distances Between Words with Parameters

  2023cites this paper
• Non-Clashing Teaching Maps for Balls in Graphs

  2023cites this paper
• Message Chains for Distributed System Verification

  2023cites this paper
• Matching Patterns with Variables Under Simon's Congruence

  2023cites this paper
• Learning Interpretable Temporal Properties from Positive Examples Only

  2022cites this paper
• Matching Patterns with Variables Under Edit Distance

  2022cites this paper
• Combinatorial Algorithms for Subsequence Matching: A Survey

  2022cites this paper
• Distinguishing Relational Pattern Languages With a Small Number of Short Strings

  2022influential citation
• Professional Training for Industrial Accident Prevention with Time Travel Games

  2022influential citation
• Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems

  2022cites this paper
• Extending Shinohara's Algorithm for Computing Descriptive (Angluin-Style) Patterns to Subsequence Patterns

  2022cites this paper
• On the structure of solution-sets to regular word equations

  2021cites this paper
• On-line synthesis of parsers for string events

  2021cites this paper
• Matching Patterns with Variables under Hamming Distance

  2021cites this paper
• Regular matching and inclusion on compressed tree patterns with constrained context variables

  2021influential citation
• AI Planning for Unique Learning Experiences: The Time Travel Exploratory Games Approach

  2021cites this paper
• Parameterized String Equations

  2021cites this paper
• Hardness Results for Constant-Free Pattern Languages and Word Equations

  2020cites this paper
• Pattern Matching with Variables

  2020influential citation
• An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries

  2020cites this paper
• Finitely distinguishable erasing pattern languages

  2020cites this paper
• On the amount of nonconstructivity in learning formal languages from text

  2020cites this paper
• 32 History of Phonology: Learnability

  2020cites this paper
• Software language engineers’ worst nightmare

  2020cites this paper
• Blocksequences of k-local Words

  2020cites this paper
• Pattern Matching with Variables: Efficient Algorithms and Complexity Results ∗

  2020influential citation
• Matching Patterns with Variables

  2019cites this paper
• Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

  2019cites this paper
• Exact Learning of Regular Pattern Languages from One Positive Example Using a Linear Number of Membership Queries

  2019cites this paper
• The teaching complexity of erasing pattern languages with bounded variable frequency

  2019cites this paper
• Finite models and the theory of concatenation

  2019cites this paper
• Regular Expressions with Backreferences: Polynomial-Time Matching Techniques

  2019cites this paper
• Intrinsic Complexity of Partial Learning

  2019cites this paper
• Computational Approaches to Predict the Non-canonical DNAs

  2019cites this paper
• Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables

  2019cites this paper
• 29. TheorietagAutomaten und Formale Sprachen Bremen, 26./27. September 2019 [width=99mm]logoUB.eps

  2019cites this paper
• Ju l 2 01 9 Matching Patterns with Variables

  2019influential citation
• The Theory of Concatenation over Finite Models

  2019cites this paper
• New results on pseudosquare avoidance

  2019cites this paper
• A Multi-agent Model for Cell Population

  2019cites this paper
• Loughborough University Institutional Repository Discontinuities in pattern inference

  2018cites this paper
• Inferring DFA without Negative Examples

  2018cites this paper
• On Matching Generalised Repetitive Patterns

  2018influential citation
• Mining HCI Data for Theory of Mind Induction

  2018influential citation
• Algebraic dependency grammar

  2018cites this paper
• Certain Query Answering on Compressed String Patterns: From Streams to Hyperstreams

  2018cites this paper
• Revisiting Shinohara's algorithm for computing descriptive patterns

  2018influential citation
• Deterministic Regular Expressions with Back-References

  2018cites this paper
• Cross-Compiling Shading Languages

  2018influential citation
• Distinguishing pattern languages with membership examples

  2017cites this paper
• Parser generation by example for legacy pattern languages

  2017influential citation
• DYNAMIC IDENTIFICATION BY ENUMERATION FOR CO-OPERATIVE KNOWLEDGE DISCOVERY

  2017cites this paper
• Institutional Repository A discontinuity in pattern inference

  2017cites this paper
• Instructions for use Title Learning a subclass of regular patterns in polynomial time Author ( s ) Case ,

  2017influential citation
• Automatic Learning from Repetitive Texts

  2017influential citation
• Patterns and Distances in Words Related to DNA Rearrangement

  2017cites this paper
• Patterns in Words Related to DNA Rearrangements

  2017cites this paper
• Generic Animats

  2017cites this paper
• Distinguishing Linear Sets and Pattern Languages With Membership Examples

  2017cites this paper
• Harmonic Structure Predicts the Enjoyment of Uplifting Trance Music

  2017cites this paper
• Institutional Repository Existence and nonexistence of descriptive patterns

  2017influential citation
• Document Spanners: From Expressive Power to Decision Problems

  2017influential citation
• Learning Pattern Languages over Groups

  2017cites this paper
• Loughborough University Institutional Repository Bad news on decision problems for patterns

  2017influential citation
• Local Patterns

  2017cites this paper
• One model for the learning of language

  2017cites this paper
• Erasing Pattern Languages Distinguishable by a Finite Number of Strings

  2017influential citation
• The Animat Path to Artificial General Intelligence

  2017cites this paper