Finite degrees of ambiguity in pattern languages

DOI10.1051/ITA/1994283-402331MaRDI QIDQ4365010zbMATH OpenOpenAlexFDO

Authors Alexandru Mateescu, Arto Salomaa

Publication date 16 March 1998

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92478, https://semanticscholar.org/paper/a25800e096abaa61300580cd77eeca2306384463

zbMATH Keywords

inductive inferencepattern languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Publication:4942653
• On the degree of ambiguity of finite automata
• On the relation between ambiguity and nondeterminism in finite automata
• Ambiguity, nondeterminism and state complexity of finite automata

Cites work

• Avoidable patterns in strings of symbols
• Finding patterns common to a set of strings
• scientific article; zbMATH DE number 3577484 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Pattern languages with and without erasing
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• Unavoidable binary patterns
• Undecidability of ground reducibility for word rewriting systems with variables

Cited in

(15)

• Bad news on decision problems for patterns
• Groups whose word problems are not semilinear
• Pattern matching with variables: a multivariate complexity analysis
• On the parameterised complexity of string morphism problems
• Bad News on Decision Problems for Patterns
• Regular and context-free pattern languages over small alphabets
• scientific article; zbMATH DE number 165816 (Why is no real title available?)
• scientific article; zbMATH DE number 929652 (Why is no real title available?)
• scientific article; zbMATH DE number 1414316 (Why is no real title available?)
• scientific article; zbMATH DE number 1453031 (Why is no real title available?)
• scientific article; zbMATH DE number 7278096 (Why is no real title available?)
• The descriptive complexity approach to LOGCFL
• A non-learnable class of E-pattern languages
• Remarks on arbitrary multiple pattern interpretations
• Discontinuities in pattern inference

This page was built for publication: Finite degrees of ambiguity in pattern languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4365010)