Efficient recognition of rational relations

DOI10.1016/0020-0190(82)90138-7MaRDI QIDQ1163370zbMATH OpenOpenAlexFDO

Authors M. Nivat, J. 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

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

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Algorithms for the Longest Common Subsequence Problem

Cited in

(10)

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

This page was built for publication: Efficient recognition of rational relations

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