Similarity in languages and programs

DOI10.1016/j.tcs.2013.05.040zbMath1296.68091OpenAlexW1998314653MaRDI QIDQ391201

Cewei Cui, Thomas R. Fischer, Zhe Dang, Oscar H. Ibarra

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.05.040

zbMATH Keywords

formal languagesShannon informationLempel-Ziv compressionsimilarity metrics

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17)

Related Items

Lossiness of communication channels modeled by transducers1, Quantifying communication in synchronized languages, Quantifying Communication in Synchronized Languages, A similarity measure for formal languages based on convergent geometric series, Information rate of some classes of non-regular languages: an automata-theoretic approach, Weights of formal languages based on geometric series with an application to automatic grading, Regular Language Distance and Entropy, Definitions and properties of entropy and distance for regular languages, Sampling automata and programs

Cites Work

• A similarity measure for graphs with low computational complexity
• The complexity of decision problems for finite-turn multicounter machines
• A note on the space complexity of some decision problems for finite automata
• Reversal-bounded multipushdown machines
• A theory of timed automata
• Graph similarity and distance in graphs
• Pushdown timed automata: A binary reachability characterization and safety verification.
• Membrane computing. An introduction.
• Graph similarity scoring and matching
• Information Rate of Some Classes of Non-regular Languages: An Automata-Theoretic Approach
• Finite state languages
• Shared Information and Program Plagiarism Detection
• Universal prediction of individual sequences
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• New Decidability Results Concerning Two-Way Counter Machines
• Execution Information Rate for Some Classes of Automata
• Mathematical Foundations of Computer Science 2003
• Stack automata and compiling
• On Context-Free Languages
• Tools and Algorithms for the Construction and Analysis of Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item