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

DOI10.1016/S0019-9958(82)80028-4zbMath0522.68064OpenAlexW1988377318MaRDI QIDQ3673125

Juhani Karhumäki, Karel II Culik, Juergen Albert

Publication date: 1982

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(82)80028-4

zbMATH Keywords

test setscontext free languagesfree monoidalgebraic systems of equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (19)

Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Unnamed Item ⋮ Polynomial size test sets for context-free languages ⋮ New techniques for proving the decidability of equivalence problem ⋮ On the system of word equations \(x_{0} u^{i}_{1} x_{1} u^{i}_{2} x_{2} u^{i}_{3} x_{3}=y_{0} v^{i}_{1} y_{1} v^{i}_{2} y_{2} v^{i}_{3} y_{3}\) \((i=0,1,2,\ldots)\) in a free monoid ⋮ On some transducer equivalence problems for families of languages ⋮ Polynomial size test sets for commutative languages ⋮ Efficient constructions of test sets for regular and context-free languages ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ A note on undercover relation ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ On binary equality sets and a solution to the test set conjecture in the binary case ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Inverse morphic equivalence on languages ⋮ On test sets for checking morphism equivalence on languages with fair distribution of letters ⋮ On cancellation properties of languages which are supports of rational power series ⋮ Test sets for morphisms with bounded delay

This page was built for publication: Test sets for context free languages and algebraic systems of equations over a free monoid