Efficient recognition of rational relations

DOI10.1016/0020-0190(82)90138-7zbMath0483.68044OpenAlexW2167426966MaRDI QIDQ1163370

Maurice Nivat, Jan van Leeuwen

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/15913

zbMATH Keywords

time complexityparallel processesbehaviour of k cooperating finite state machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Theory of operating systems (68N25)

Related Items

Rational equivalence relations ⋮ On the parallel complexity of loops ⋮ Quasi-automatic semigroups ⋮ On recognising words that are squares for the shuffle product ⋮ Parallel parsing on a one-way linear array of finite-state machines ⋮ Algorithmic and algebraic aspects of unshuffling permutations ⋮ A constant time string shuffle algorithm on reconfigurable meshes ⋮ Recognizing binary shuffle squares is \textsf{NP}-hard ⋮ The Shuffle Product: New Research Directions ⋮ On efficient recognition of transductions and relations

Cites Work

• Unnamed Item
• Algorithms for the Longest Common Subsequence Problem