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

behaviour of k cooperating finite state machinesparallel processestime complexity

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(11)

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

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)