Efficient recognition of rational relations

DOI10.1016/0020-0190(82)90138-7zbMATH Open0483.68044OpenAlexW2167426966MaRDI QIDQ1163370FDOQ1163370

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

• Title not available (Why is that?)
• Algorithms for the Longest Common Subsequence Problem

Cited In (10)

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

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)